QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #291368 | #5823. 海星 | Nwayy | 0 | 28ms | 20400kb | C++14 | 1.4kb | 2023-12-26 13:55:53 | 2023-12-26 13:55:54 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define N 100005
#define int long long
int n,m,i,j,ans,p[N],x,y,d[N],s,k,ru[N],a[N],f[N][5];
vector<int>G[N];
int dfs(int k,int flag){
if(k>n) return 0;
if(f[k][flag]!=-1) return f[k][flag];
int g=-1e18;
// printf("%lld %lld %lld\n",k,flag,s);
if(flag==0) g=max(g,dfs(k+1,flag));
if(flag==1) g=max(g,dfs(k+1,0));
if(flag==2) g=max(g,dfs(k+1,1));
if(flag==0){
g=max(g,dfs(k+1,1)+abs(p[k]-p[k-1]));
if(k<n) g=max(g,dfs(k+1,2)+abs(p[k]-(p[k-1]+p[k+1])));
if(k<n) g=max(g,dfs(k+1,2)+abs(p[k]-p[k+1]));
}
if(flag==1 && k<n) g=max(g,dfs(k+1,2)+abs(p[k]-p[k+1]));
return f[k][flag]=g;
}
signed main(){
scanf("%lld",&n);
for(i=1;i<=n;i++) scanf("%lld",&p[i]);
for(i=1;i<n;i++){
scanf("%lld%lld",&x,&y);
G[x].push_back(y),G[y].push_back(x);
d[x]++,d[y]++;
ru[x]++,ru[y]++;
}
sort(d+1,d+1+n);
if(n==1){
puts("0");
return 0;
}
if(n==2){
printf("%lld\n",abs(p[1]-p[2]));
return 0;
}
if(d[1]==1 && d[2]==1 && d[n]==2){
int l=0;
for(i=1;i<=n;i++) if(ru[i]==1 && !s) s=i;
while(s){
a[++m]=s;
int flag=0;
for(int y:G[s]){
if(y!=l) flag=1,l=s,s=y;
}
if(!flag) break;
// printf("%lld %lld\n",l,s);
}
memset(f,-1,sizeof(f));
ans=dfs(1,1);
// for(i=1;i<=m;i++) printf("%lld ",a[i]);
// puts("");
printf("%lld\n",ans);
}
return 0;
}
/*
4
1 2 3 4
1 2
2 3
3 4
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 6ms
memory: 10632kb
input:
33331 -11171186 515439 98965039 -76317393 16735754 65157773 -68894376 -5035890 63842297 62703445 19490093 -19348988 36626070 -63191544 75774675 36234673 25724106 50267065 95991004 -82314232 -1707507 21500141 -55977458 20099787 93919133 -61954505 10399933 37981621 -43972867 -55397173 64852507 -634294...
output:
result:
wrong answer 1st lines differ - expected: '841990039350', found: ''
Test #2:
score: 0
Wrong Answer
time: 15ms
memory: 12932kb
input:
66733 95890724 -97180087 10701157 -10302967 -56760887 72959390 42732829 -91968513 -10763389 -80502496 18023509 85926697 -73480245 35214859 75110409 -26337972 94380335 -7380945 81742484 99347886 -95766726 -51556891 8860897 73971259 -47084371 40118674 -39454765 84062321 57271285 46043487 -16495828 -72...
output:
result:
wrong answer 1st lines differ - expected: '1675502896833', found: ''
Test #3:
score: 0
Time Limit Exceeded
input:
55818 95576832 -40406540 -77562724 -86962223 -86355864 -14707525 -23284928 -55013846 -8797620 -32039919 31497563 -84079189 7120642 -39679632 -84793218 -79671203 22810005 -78303679 -27225316 96630550 -9567274 -80702726 98257718 60033511 85660197 61232007 62647537 -26612843 42809208 49207326 33106201 ...
output:
result:
Test #4:
score: 0
Time Limit Exceeded
input:
91488 -37356407 70273299 -60793880 -81403777 26478480 -34922436 -97890613 50474190 86412614 17362759 30833296 -34256525 11556777 21201579 21147564 49884363 -61234378 -39215570 -77080013 -66799487 -13159339 5668756 24773374 82719762 -50391822 63067832 -41251234 -45854335 31866899 17585770 76346192 18...
output:
result:
Test #5:
score: 0
Wrong Answer
time: 14ms
memory: 17252kb
input:
61092 -32373791 85985862 50942239 -32896750 67163226 -88020477 89587848 13623756 -87727832 25401341 90845091 -99650981 -43504678 -44485246 -83480211 -31564851 -27146298 -9527223 51505439 30561978 63627461 -51468118 -23806772 -15592067 70166666 -3488822 -89899072 -54152707 61250000 9159108 -2943889 4...
output:
2596478523366
result:
wrong answer 1st lines differ - expected: '2598174943942', found: '2596478523366'
Test #6:
score: 0
Wrong Answer
time: 28ms
memory: 20400kb
input:
94029 -27391174 -65418446 24762503 77694422 74964844 91764613 14982163 -10699337 -40951873 -83831888 81523459 65388804 -31589647 80879853 33029128 -28920360 -58524160 -95273096 85294739 -22860576 -10278020 31425752 77804686 33124988 87569594 66739481 88867080 63643987 42865412 78510950 -89192521 -12...
output:
3992112321227
result:
wrong answer 1st lines differ - expected: '3994288382684', found: '3992112321227'
Test #7:
score: 0
Wrong Answer
time: 11ms
memory: 11908kb
input:
37815 72986234 46218421 -92142995 22940263 -51535509 -60927696 25100989 -276786 -43307684 -48002472 -42269299 -6381350 -41510853 57401248 -69736412 25447817 73479189 21767399 -66290763 21544721 -63064466 81458555 -3274254 30869267 -37596193 97638880 46154839 2034100 -75586225 45459932 2617444 580047...
output:
result:
wrong answer 1st lines differ - expected: '1898177776617', found: ''
Test #8:
score: 0
Wrong Answer
time: 14ms
memory: 12572kb
input:
57893 24162311 96767788 61802773 -53223704 -75735497 81664175 -23248708 -98216048 -49451242 47944013 -60647681 -59327448 -66603953 81688992 -61386635 99535541 39605703 73604678 28138617 -53974258 -70742530 -19547670 35051204 27237673 64515468 78810378 37552041 39545443 40274254 -35113952 18667785 65...
output:
result:
wrong answer 1st lines differ - expected: '2903116466949', found: ''
Test #9:
score: 0
Wrong Answer
time: 7ms
memory: 9308kb
input:
22262 79028027 -38068784 93419573 -84167706 -58826963 80129696 34827899 -71598389 -55386224 89551685 -1780032 -89709755 70585785 -99828150 74583280 -58212897 53317984 41207699 -51628902 76695264 -7800274 -62002987 83614479 -11821436 41029875 -38843498 -2826518 77085681 23323956 -18881588 -71698064 -...
output:
result:
wrong answer 1st lines differ - expected: '1117798967714', found: ''
Test #10:
score: 0
Wrong Answer
time: 18ms
memory: 12248kb
input:
57899 65256064 -81736780 -93771845 -32702714 -24771253 15750201 9958033 82132633 76323779 70133194 2619146 -36540696 2408835 52625422 -50641708 -15127271 -61323743 43840072 30961962 97444188 -22186191 -36173544 90098167 -78043532 38044570 -90710994 29068826 56013279 -81170795 59787380 25960103 -8339...
output:
result:
wrong answer 1st lines differ - expected: '2890093707385', found: ''
Test #11:
score: 0
Wrong Answer
time: 13ms
memory: 12668kb
input:
65535 -58178985 96514995 -68371098 542628 75485904 -48819657 -19687829 78739995 36486631 -23577568 -91343497 -45004634 -75175484 -79676281 -39722449 56568339 80807233 -26427013 -78839918 80628279 6195245 95836900 -2157545 -81272507 91841194 24828298 -13223423 -82384969 -75486219 -9946260 43037365 -3...
output:
result:
wrong answer 1st lines differ - expected: '2523505648073', found: ''
Test #12:
score: 0
Wrong Answer
time: 12ms
memory: 13356kb
input:
65535 20805949 88919022 -81058737 -14388874 -72213374 10778248 72548233 -52234544 -6061081 66555934 -75630933 41612666 -42228918 63798020 -83634798 -10393560 -34374953 31739738 -13582443 -75967832 -86946009 -81171605 47245132 -49750706 38240813 74650962 -79088681 93742682 -14605009 -98253778 9144685...
output:
result:
wrong answer 1st lines differ - expected: '2511325948959', found: ''
Test #13:
score: 0
Wrong Answer
time: 8ms
memory: 11156kb
input:
65535 89725432 -13644226 -41727682 75712349 12970479 70376153 26868440 16790918 56423934 51656710 35048906 -19751340 95750374 -25610809 -65463001 27677267 7494281 46957909 -43292243 -75512522 -75054538 3904036 96647809 86803820 -15359568 29506351 -39921212 17851637 79159330 -91594021 77772189 -47001...
output:
result:
wrong answer 1st lines differ - expected: '2512147155027', found: ''
Test #14:
score: 0
Wrong Answer
time: 16ms
memory: 12736kb
input:
65535 -31289635 11642931 -64480772 60780847 65271202 -7941798 24137228 85816380 13876222 46822938 50761469 23917379 -61237610 -82136508 90624651 22799514 -12720631 -94875341 21965232 29975514 93888355 88979678 41017761 -81674381 26007326 -77722405 -753744 36927867 -59959460 20098463 64097528 8255408...
output:
result:
wrong answer 1st lines differ - expected: '2524924391007', found: ''
Test #15:
score: 0
Wrong Answer
time: 4ms
memory: 10176kb
input:
10096 69858238 -55660119 -47237653 -30113370 76781150 -48693571 -66973456 -55813012 -23286888 78050033 61006322 -62091234 42370271 27877974 -78168867 76908903 39994491 -19787991 43459869 -13545255 50744464 68267711 60584667 7072582 98908050 61815876 61023363 71951508 -41592277 12477203 90383274 5825...
output:
result:
wrong answer 1st lines differ - expected: '396095618452', found: ''
Test #16:
score: 0
Wrong Answer
time: 0ms
memory: 9400kb
input:
4437 26423344 89373990 -93739235 -92819276 -84442461 -92640841 5701777 -23166121 61316354 -95695276 -68588684 -57034153 5647502 -51033681 49437746 99658733 -40527233 4208491 70409789 -16396598 -55609977 31104750 -52329556 -62486704 76079169 -37475857 -46743268 -71924622 64879717 16978873 -78988296 -...
output:
result:
wrong answer 1st lines differ - expected: '172550095391', found: ''
Test #17:
score: 0
Wrong Answer
time: 12ms
memory: 10032kb
input:
40645 3407065 28238385 68003322 82379451 -20502460 34676191 -30339739 -34135417 -57821409 48985313 116385 -28029723 90527442 54370930 -37653446 -13711698 -36488191 -96512752 -17843258 84917115 -86075376 -66507087 -19700391 6821655 11850185 -22079788 85859006 -65685885 8415532 75747957 -95792517 8632...
output:
result:
wrong answer 1st lines differ - expected: '1597596177653', found: ''
Test #18:
score: 0
Wrong Answer
time: 17ms
memory: 10716kb
input:
58096 -21520940 14906872 -76529712 -97115412 -39035970 -10898467 15700388 14986513 -1985788 77896105 -10794040 91260360 38325660 89785735 -77188066 -96289624 26690803 70767098 12410493 -41057316 -84216973 71537112 -88437995 18251143 -87565662 -93457909 -54043965 34319435 50348286 -91620647 -39152263...
output:
result:
wrong answer 1st lines differ - expected: '2295981035832', found: ''
Test #19:
score: 0
Wrong Answer
time: 18ms
memory: 12384kb
input:
58742 49309979 17064418 91341883 36626211 78574509 82482129 54033614 -43882069 -76626851 76435284 -28054178 -9921358 41005796 74993210 38225930 73572671 85848904 66870992 13954686 23734782 -52193830 -8020005 -89449220 80999468 -27295929 -7875578 -58737621 1026085 -52319712 56699150 -45290942 -664328...
output:
result:
wrong answer 1st lines differ - expected: '2305394084092', found: ''
Test #20:
score: 0
Wrong Answer
time: 15ms
memory: 12704kb
input:
64098 68081705 59817009 -15971018 -15193981 65763006 -30937900 -80243926 59363283 -9992164 -79919403 26417299 96085299 -15257349 -76953181 18273634 -94827829 -20399747 52876535 62913713 -62479083 -64742361 12685176 -30217045 -26774642 -45771535 -38780887 -87046419 -31561031 -70482614 -93942311 -9001...
output:
result:
wrong answer 1st lines differ - expected: '2520090381442', found: ''