QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#625441 | #6107. One Path | strlen_s_ | AC ✓ | 31ms | 98232kb | C++17 | 2.1kb | 2024-10-09 19:20:10 | 2024-10-09 19:20:10 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=2005;
const ll inf=1e18;
int h[N],nex[N<<1],to[N<<1],e[N<<1],tot;
ll dp[N][N][3],ans[N];
ll g[N][3],f[N][3];
int siz[N];
int d[N],rt;
void add(int x,int y,int z){to[++tot]=y,e[tot]=z,nex[tot]=h[x],h[x]=tot;}
void dfs(int u,int fa){
siz[u]=1;
if(d[u]==1){dp[u][0][1]=dp[u][1][2]=dp[u][1][0]=0;return;}
for(int i=h[u];i;i=nex[i]){
int v=to[i];
if(v==fa)continue;
dfs(v,u);
siz[u]+=siz[v];
}
g[0][1]=0;
for(int i=h[u],sz=0;i;i=nex[i]){
int v=to[i];
if(v==fa)continue;
for(int j=0;j<=sz;j++)f[j][0]=g[j][0],f[j][1]=g[j][1],g[j][0]=g[j][1]=-inf;
for(int j=0;j<=sz;j++)
for(int k=0;k<=siz[v];k++){
ll x=max(dp[v][k][1],dp[v][k][0]+e[i]);
g[j+k][0]=max({g[j+k][0],f[j][0]+x,f[j][1]+dp[v][k][0]});
g[j+k][1]=max(g[j+k][1],f[j][1]+x);
}
sz+=siz[v];
}
for(int i=0;i<=siz[u];i++)dp[u][i][0]=g[i][0],dp[u][i][1]=g[i][1],g[i][0]=g[i][1]=-inf;
g[0][0]=0;
for(int i=h[u],sz=0;i;i=nex[i]){
int v=to[i],w=e[i];
if(v==fa)continue;
for(int j=0;j<=sz;j++)
for(int k=0;k<3;k++)
f[j][k]=g[j][k],g[j][k]=-inf;
for(int j=0;j<=sz;j++)
for(int k=0;k<=siz[v];k++){
ll x=max(dp[v][k][1],dp[v][k][0]+w);
g[j+k][0]=max(g[j+k][0],f[j][0]+x);
g[j+k][1]=max({g[j+k][1],f[j][1]+x,f[j][0]+dp[v][k][2]+w});
g[j+k][2]=max({g[j+k][2],f[j][2]+x,f[j][1]+dp[v][k][2]+w});
}
sz+=siz[v];
}
for(int i=0;i<=siz[u];i++)dp[u][i][2]=g[i][1],dp[u][i][0]=max({dp[u][i][0],g[i+1][2],g[i][1]}),g[i][0]=g[i][1]=g[i][2]=-inf;
}
int n,k;
signed main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n>>k;
for(int i=1,x,y,z;i<n;i++){
cin>>x>>y>>z;
add(x,y,z),add(y,x,z);
d[x]++,d[y]++;
}
if(n==2){
for(int i=0;i<=k;i++)cout<<e[1]<<' ';cout<<'\n';
return 0;
}
rt=1;while(d[rt]==1)rt++;
memset(dp,0xcf,sizeof(dp));memset(g,0xcf,sizeof(g));
dfs(rt,0);
for(int i=0;i<=k;i++)ans[i]=max((i?ans[i-1]:-inf),dp[rt][i+1][0]);
for(int i=0;i<=k;i++)cout<<ans[i]<<' ';cout<<'\n';
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 4ms
memory: 97884kb
input:
5 1 1 3 2 4 5 4 3 4 3 2 3 7
output:
14 16
result:
ok 2 number(s): "14 16"
Test #2:
score: 0
Accepted
time: 3ms
memory: 98000kb
input:
7 2 1 2 4 2 3 6 2 4 2 4 5 5 2 6 1 4 7 3
output:
13 20 21
result:
ok 3 number(s): "13 20 21"
Test #3:
score: 0
Accepted
time: 4ms
memory: 97968kb
input:
50 2000 3 34 1 37 39 58720256 17 24 14680064 28 39 1 25 38 1 21 29 1 3 30 1 26 36 1 5 48 14336 4 22 1 26 41 1 41 44 1 5 14 1 23 25 28672 40 41 224 27 39 1 4 20 7340032 7 47 939524096 11 46 114688 30 49 3584 34 44 1 7 35 1 10 29 1 27 33 29360128 16 36 56 8 28 1 13 38 57344 34 45 896 15 35 469762048 1...
output:
1409286145 1761607683 1849688069 1871708167 1877213193 1878589451 1878933517 1879019535 1879041041 1879046419 1879047765 1879048103 1879048160 1879048160 1879048160 1879048160 1879048160 1879048160 1879048160 1879048160 1879048160 1879048160 1879048160 1879048160 1879048160 1879048160 1879048160 187...
result:
ok 2001 numbers
Test #4:
score: 0
Accepted
time: 9ms
memory: 97936kb
input:
10 5 1 4 10 3 7 138 1 9 162 4 10 113 4 6 12 5 6 171 2 10 31 7 8 12 7 10 132
output:
566 769 781 781 781 781
result:
ok 6 numbers
Test #5:
score: 0
Accepted
time: 0ms
memory: 3600kb
input:
2 0 1 2 340241821
output:
340241821
result:
ok 1 number(s): "340241821"
Test #6:
score: 0
Accepted
time: 20ms
memory: 97988kb
input:
2000 0 450 1620 747893383 103 1602 466748018 746 1996 468886757 430 764 455748265 1201 1275 111041658 244 802 715844971 611 899 125646661 1105 1633 478144612 180 573 823370712 161 1018 67225549 1512 1915 538711443 829 1871 761057722 1297 1499 576790037 1492 1832 983172784 1486 1902 78076400 1206 121...
output:
83343544566
result:
ok 1 number(s): "83343544566"
Test #7:
score: 0
Accepted
time: 0ms
memory: 3640kb
input:
2 2000 1 2 128840350
output:
128840350 128840350 128840350 128840350 128840350 128840350 128840350 128840350 128840350 128840350 128840350 128840350 128840350 128840350 128840350 128840350 128840350 128840350 128840350 128840350 128840350 128840350 128840350 128840350 128840350 128840350 128840350 128840350 128840350 128840350 ...
result:
ok 2001 numbers
Test #8:
score: 0
Accepted
time: 10ms
memory: 98044kb
input:
1139 1252 115 643 947372561 358 529 121247876 22 177 680088711 70 692 912515870 602 1032 172209848 908 1064 871258945 1052 1085 268011860 88 405 978751838 65 913 486052321 75 496 113634888 654 841 834034656 209 409 142094069 674 700 147589677 828 885 666263686 486 685 480409259 111 839 151780996 634...
output:
59768151302 90240365913 110773200826 126071855751 138635934480 150183113228 161491697716 171973479232 180896150286 189526447107 198151654732 205944843996 212594288075 218867722405 224758314304 230517398967 236194246382 241771608481 247290975973 252679174462 257726719571 262623730494 267497011096 272...
result:
ok 1253 numbers
Test #9:
score: 0
Accepted
time: 20ms
memory: 98096kb
input:
1859 96 699 1243 527467234 415 1097 309143472 834 889 56461226 89 922 696975323 249 557 760384934 1620 1690 911166764 609 1585 141960232 523 539 309575211 42 1345 916022932 246 941 347574724 28 1495 182056532 574 1105 916959837 16 643 180912142 320 1019 581796393 382 1057 499874329 947 953 301695678...
output:
73034441563 106249124134 137863093980 161415598143 181010417474 194193377374 207123967837 219361720623 231431488822 243379406510 254900175123 263921423452 272660640110 281348087243 289617350632 297744866034 305363066315 312852129266 319938484905 326850253133 333691085598 340478497934 347177411972 35...
result:
ok 97 numbers
Test #10:
score: 0
Accepted
time: 7ms
memory: 98108kb
input:
1987 237 795 1859 538237294 345 876 821314172 7 1559 906510259 242 1432 762788662 1453 1749 364000108 1209 1359 453259815 405 1598 150980044 572 1404 562800021 907 986 963629668 449 513 92145600 411 1003 862695660 410 713 81673798 461 1357 130367299 834 979 352931273 939 1844 834620340 410 1777 9425...
output:
56609927740 97759271260 123612193903 146444416692 164666274007 182780268884 199806807167 214231799004 228651823319 239930531652 250252397021 260203803621 270153616316 279703671233 289132717988 298396751533 307581154444 316703572602 325729593393 334470860906 343177322356 351095333882 358697251377 365...
result:
ok 238 numbers
Test #11:
score: 0
Accepted
time: 7ms
memory: 98016kb
input:
1411 1081 43 1295 334569570 158 826 998830872 32 520 790860304 1217 1306 293047564 81 515 860829709 668 996 713497619 500 1022 181765242 223 1037 402696222 22 234 900851429 725 1088 897436523 1135 1370 208306139 1074 1305 614845501 80 1173 861704641 632 1332 573535182 603 1406 546933987 299 357 5651...
output:
61653087225 92319773874 117264674880 137368780628 155288661230 170285398213 184865912070 197394760447 207731774764 217033899171 226169626282 234109350786 241978606486 249717804030 256769892676 263336321508 269732422010 276112863169 282199153793 288117750481 293957463672 299512444779 305057595916 310...
result:
ok 1082 numbers
Test #12:
score: 0
Accepted
time: 12ms
memory: 98056kb
input:
1539 1221 1116 1206 952040395 1358 1436 770882525 854 1487 553269355 866 953 858516304 94 1032 820500926 43 107 538457923 788 1258 510373107 832 1383 902758419 536 708 152282105 272 1036 850934532 1068 1168 656625369 804 1528 232691777 945 1130 210785119 775 1452 763524384 108 585 981053184 442 1296...
output:
64781611118 86390722759 106904313442 126616701336 140701817647 154757467052 168630614764 181390842451 193236212444 205063950667 215967392296 226730711439 237491364418 247124934519 256399117075 265177862910 273824647078 282182672565 290084350175 297597801116 304894488986 311937945295 318844597499 325...
result:
ok 1222 numbers
Test #13:
score: 0
Accepted
time: 0ms
memory: 3644kb
input:
2 1122 1 2 27411274
output:
27411274 27411274 27411274 27411274 27411274 27411274 27411274 27411274 27411274 27411274 27411274 27411274 27411274 27411274 27411274 27411274 27411274 27411274 27411274 27411274 27411274 27411274 27411274 27411274 27411274 27411274 27411274 27411274 27411274 27411274 27411274 27411274 27411274 274...
result:
ok 1123 numbers
Test #14:
score: 0
Accepted
time: 11ms
memory: 97992kb
input:
2000 477 817 1613 356254474 248 1669 991109385 327 1628 421291429 1236 1878 910648092 780 1660 278229822 569 1867 725529058 418 686 420432952 1424 1967 988813595 581 1175 202022092 1257 1740 686615740 352 832 536745041 295 1152 862358989 966 1005 861433533 440 526 412533652 1341 1873 106024555 1244 ...
output:
67235179780 99370870321 122966082198 143046584075 159656170072 174157703744 187758195193 201288370806 214473876547 227048011582 238597224590 249316319712 259795358457 270097425664 280074090311 289695086448 298965283082 308101456012 316941136552 325358303906 333755857196 341695399397 349117854532 356...
result:
ok 478 numbers
Test #15:
score: 0
Accepted
time: 19ms
memory: 98044kb
input:
1933 0 631 1453 301574362 670 1445 908820044 10 1215 311953510 388 568 132016918 1589 1774 229370374 532 1010 955269448 737 1389 637639793 959 1786 651118866 61 1109 11533045 461 1390 874807689 1488 1538 869753699 594 1544 75727291 1081 1368 588420426 1214 1344 159817475 375 1330 641932392 68 578 68...
output:
86978457112
result:
ok 1 number(s): "86978457112"
Test #16:
score: 0
Accepted
time: 12ms
memory: 97988kb
input:
1927 2000 332 1530 493555677 168 326 493378666 530 1236 535282116 176 1766 105136777 85 1558 812201103 313 1230 701928002 14 658 936300281 281 509 47001615 175 1204 152130180 256 603 744792426 335 494 947591544 932 1904 672997484 1400 1413 204357419 586 1355 73661367 978 1776 274383489 716 1680 9231...
output:
51669034567 82067124757 104902748075 127340300141 147052175311 165899641368 182971159746 198221149950 212405129674 225313986944 236309474108 246440330251 256446620314 266308651750 275900624721 285460321159 294584276765 303448566703 312308988758 321020545653 329179604583 337268126247 344908641784 352...
result:
ok 2001 numbers
Test #17:
score: 0
Accepted
time: 11ms
memory: 97992kb
input:
1999 1999 246 541 718549795 185 1526 699871023 1049 1075 859263071 206 1902 618784659 61 1112 18221371 1411 1466 158881611 356 1325 179607327 250 1117 623566900 33 1492 343401884 871 1620 130304408 222 1719 127219136 781 1516 253059487 808 1769 814457515 686 904 650394117 996 1440 344055650 321 1976...
output:
71267431325 111280520317 140393231139 164403603026 181000860377 196404911868 211327831737 225623393244 238080353278 249657854676 260294116582 270823408346 280576300045 290318251670 299787598171 308917096789 317690152218 325766117932 333724778634 341462281963 348893097690 355920120543 362526885723 36...
result:
ok 2000 numbers
Test #18:
score: 0
Accepted
time: 11ms
memory: 98068kb
input:
1999 2000 1061 1266 664280353 221 1818 397746258 13 1779 87167245 1123 1528 833742837 137 634 992027589 1073 1093 115027682 670 1149 247113477 1235 1740 974150088 758 1975 837538008 863 1173 989199643 1136 1683 214893589 384 763 456019260 979 1660 159881516 587 1179 796782807 1707 1841 789775650 181...
output:
85997460747 128088260223 152760908534 170437672310 186348508020 200426900823 213867058037 226540405784 238734389092 250706259245 262153206495 272795379288 282533606428 291807369483 300873151329 309912245757 318556682590 327069271299 335407701809 343516673643 351406178497 359193539926 366964599113 37...
result:
ok 2001 numbers
Test #19:
score: 0
Accepted
time: 15ms
memory: 98060kb
input:
2000 1999 378 1734 23318723 829 1112 413304625 528 1582 569433420 934 1181 756023969 93 968 354583831 1304 1787 699996460 1041 1454 571219223 387 787 666292778 1121 1903 496663085 84 1174 464947338 458 686 360863108 964 1953 148516304 572 720 746487102 537 787 645775712 115 1249 324854607 128 1985 9...
output:
68901798177 97000172190 119656621820 139797724077 159264439474 175958917741 192556819603 207652350606 221884717679 235228151021 247115447370 257968741690 268319164934 277611401360 286581373016 295433028989 303172596930 310504050141 317771312825 324938637730 332017251683 338701464496 345317900776 351...
result:
ok 2000 numbers
Test #20:
score: 0
Accepted
time: 11ms
memory: 98088kb
input:
2000 2000 128 466 931497867 889 1882 58748942 957 1153 901867050 13 109 890213780 152 1573 520560154 207 1335 85417171 1016 1778 122959691 1699 1993 106709360 345 748 132255317 833 1975 61665020 857 1126 148676046 143 1114 518456424 806 1085 897926879 1523 1720 300332215 1136 1711 89687829 243 627 3...
output:
100594764511 130036946447 157445013049 175498253608 189190939331 202648700325 216092969383 229001647648 241597181745 253043720429 264145447117 274688901772 284801560800 294423391817 303834955358 312797642187 321377177995 329412204227 337231794825 344543733178 351814405385 358701153055 365550285868 3...
result:
ok 2001 numbers
Test #21:
score: 0
Accepted
time: 7ms
memory: 98076kb
input:
2000 2000 118 1221 13012340 651 1980 659742801 1805 1978 721143653 651 742 110218824 1302 1771 702313088 339 1814 618431349 1117 1849 908296203 458 1233 334410044 954 1951 596189034 507 1374 166721094 300 1598 468467068 483 1161 626776195 849 1640 297003076 1032 1478 913563506 579 850 988354764 941 ...
output:
63142158264 99682581437 122866161726 145827679716 165841942833 184219865446 202212056839 215972445753 228870443457 241126804713 252987623531 263842880083 274648955792 285045240006 295159500569 303342158718 311087087673 318792911149 326478576809 333862878321 341220363320 348532459714 355761058874 362...
result:
ok 2001 numbers
Test #22:
score: 0
Accepted
time: 16ms
memory: 97996kb
input:
1999 1999 865 967 462237029 4 772 843431891 1134 1415 11343807 749 1406 296978536 379 1175 170243393 1375 1812 895194997 772 1288 646926338 401 1783 95720864 589 1624 977470728 738 1146 606456673 656 1804 808753625 349 1305 662341811 1103 1160 793298257 215 346 64166919 1176 1224 309310390 607 1277 ...
output:
13480756087 25624866435 37001979783 47153545662 57124589898 66029761194 74861879700 83598040058 91793228193 99937431261 107838321675 115468243606 123082184542 130329565644 137515097675 144521373558 151432122204 158187448580 164938827032 171643016750 178153948942 184467175921 190777800431 19695495863...
result:
ok 2000 numbers
Test #23:
score: 0
Accepted
time: 7ms
memory: 98064kb
input:
2000 2000 176 300 102142910 211 1544 388129165 1059 1441 620150505 978 1233 779832879 905 1175 634815854 1186 1589 418299985 223 1661 401799347 223 1870 876075812 1149 1211 675037357 81 1290 734722948 797 1895 938505893 543 1775 863818843 498 1397 930705471 1399 1423 99136835 704 1818 747744439 677 ...
output:
14516810448 26632165986 37618789666 48524763088 58595823980 68175412240 77258805946 85938563072 94446503795 102831657097 110827128662 118622716179 126071332182 133249088914 140351748565 147429941874 154487196894 161256708308 167883788842 174356645479 180798165427 187173505120 193255681797 1993274557...
result:
ok 2001 numbers
Test #24:
score: 0
Accepted
time: 16ms
memory: 98112kb
input:
1999 1999 865 967 256 4 772 1 1134 1415 64 749 1406 32768 379 1175 4096 1375 1812 67108864 772 1288 128 401 1783 8388608 589 1624 134217728 738 1146 4096 656 1804 16 349 1305 1 1103 1160 64 215 346 256 1176 1224 524288 607 1277 128 1559 1608 4194304 974 1984 1048576 509 1098 524288 473 552 256 643 7...
output:
2996897073 5162245810 7260454616 9054568921 10693136858 12320807515 13939836498 15337114970 16720976114 18080102746 19422380882 20698514503 21907592391 23098831101 24243997341 25379605178 26478957562 27577906220 28661453872 29740997680 30817131812 31892127196 32966787792 34040707038 35114537118 3618...
result:
ok 2000 numbers
Test #25:
score: 0
Accepted
time: 7ms
memory: 98076kb
input:
2000 2000 176 300 512 211 1544 16777216 1059 1441 16 978 1233 262144 905 1175 8388608 1186 1589 16 223 1661 64 223 1870 2097152 1149 1211 64 81 1290 131072 797 1895 4194304 543 1775 4194304 498 1397 1048576 1399 1423 16777216 704 1818 262144 677 1846 16 712 1419 524288 182 446 8388608 958 1957 1 561...
output:
2596446634 4836402091 7017512093 9135136837 11024768989 12758497726 14411320820 16026125150 17569630526 18996947950 20348210788 21691200638 23002379880 24215081287 25414985543 26574055037 27702339384 28804691356 29897902492 30988542657 32074875323 33154942996 34233371007 35311176640 36387240553 3746...
result:
ok 2001 numbers
Test #26:
score: 0
Accepted
time: 19ms
memory: 98224kb
input:
1999 1999 865 882 462237029 4 146 843431891 464 1415 11343807 749 1369 296978536 200 379 170243393 1165 1812 895194997 772 1263 646926338 915 1783 95720864 815 1624 977470728 681 738 606456673 1299 1804 808753625 72 1305 662341811 126 1103 793298257 346 1052 64166919 385 1224 309310390 1277 1760 138...
output:
1006569662256 1006569662256 1006569662256 1006569662256 1006569662256 1006569662256 1006569662256 1006569662256 1006569662256 1006569662256 1006569662256 1006569662256 1006569662256 1006569662256 1006569662256 1006569662256 1006569662256 1006569662256 1006569662256 1006569662256 1006569662256 100656...
result:
ok 2000 numbers
Test #27:
score: 0
Accepted
time: 13ms
memory: 98136kb
input:
2000 2000 176 478 102142910 211 1185 388129165 260 1059 620150505 978 1964 779832879 905 1506 634815854 1186 1372 418299985 223 1274 401799347 1607 1870 876075812 184 1211 675037357 4 1290 734722948 797 1519 938505893 454 543 863818843 158 498 930705471 832 1423 99136835 573 704 747744439 677 998 58...
output:
1011630904032 1011630904032 1011630904032 1011630904032 1011630904032 1011630904032 1011630904032 1011630904032 1011630904032 1011630904032 1011630904032 1011630904032 1011630904032 1011630904032 1011630904032 1011630904032 1011630904032 1011630904032 1011630904032 1011630904032 1011630904032 101163...
result:
ok 2001 numbers
Test #28:
score: 0
Accepted
time: 19ms
memory: 98228kb
input:
1999 1999 865 882 256 4 146 1 464 1415 64 749 1369 32768 200 379 4096 1165 1812 67108864 772 1263 128 915 1783 8388608 815 1624 134217728 681 738 4096 1299 1804 16 72 1305 1 126 1103 64 346 1052 256 385 1224 524288 1277 1760 128 985 1559 4194304 679 974 1048576 509 1338 524288 473 1385 256 643 1772 ...
output:
69294815506 69294815506 69294815506 69294815506 69294815506 69294815506 69294815506 69294815506 69294815506 69294815506 69294815506 69294815506 69294815506 69294815506 69294815506 69294815506 69294815506 69294815506 69294815506 69294815506 69294815506 69294815506 69294815506 69294815506 69294815506 ...
result:
ok 2000 numbers
Test #29:
score: 0
Accepted
time: 15ms
memory: 98204kb
input:
2000 2000 176 478 512 211 1185 16777216 260 1059 16 978 1964 262144 905 1506 8388608 1186 1372 16 223 1274 64 1607 1870 2097152 184 1211 64 4 1290 131072 797 1519 4194304 454 543 4194304 158 498 1048576 832 1423 16777216 573 704 262144 677 998 16 712 1963 524288 182 1256 8388608 84 1957 1 384 1889 5...
output:
72907974573 72907974573 72907974573 72907974573 72907974573 72907974573 72907974573 72907974573 72907974573 72907974573 72907974573 72907974573 72907974573 72907974573 72907974573 72907974573 72907974573 72907974573 72907974573 72907974573 72907974573 72907974573 72907974573 72907974573 72907974573 ...
result:
ok 2001 numbers
Test #30:
score: 0
Accepted
time: 16ms
memory: 98136kb
input:
1999 1999 865 956 462237029 4 666 843431891 1415 1667 11343807 749 1369 296978536 379 528 170243393 1165 1812 895194997 772 1974 646926338 1573 1783 95720864 1015 1624 977470728 738 1333 606456673 1299 1804 808753625 72 1305 662341811 126 1103 793298257 158 346 64166919 221 1224 309310390 1277 1760 ...
output:
511685828749 513649657954 515549713394 517445133638 519319536303 521189904111 523059839658 524909176860 526750323314 528587690566 530415348642 532232747980 534046345752 535850285912 537652521850 539444055582 541229371111 543013041032 544795011542 546572398892 548349216036 550122206344 551889736574 5...
result:
ok 2000 numbers
Test #31:
score: 0
Accepted
time: 23ms
memory: 98116kb
input:
2000 2000 176 607 102142910 211 1185 388129165 260 1059 620150505 978 1964 779832879 463 905 634815854 582 1186 418299985 223 1274 401799347 1607 1870 876075812 1211 1980 675037357 4 1290 734722948 797 1204 938505893 543 1120 863818843 158 498 930705471 667 1423 99136835 76 704 747744439 677 998 586...
output:
502391026753 504331613111 506266052188 508191111478 510114913414 512034293942 513947761638 515854792702 517748993303 519638541242 521506088912 523372998369 525235942584 527088346756 528927103695 530762242147 532591489290 534420620849 536245284640 538069892594 539886995423 541703278013 543519298002 5...
result:
ok 2001 numbers
Test #32:
score: 0
Accepted
time: 16ms
memory: 98124kb
input:
1999 1999 427 467 64 1331 1700 1 1170 1966 4096 815 1842 4096 417 851 1024 916 1235 134217728 1491 1647 2 1363 1531 134217728 847 1383 256 958 1355 2 269 1957 131072 134 495 8192 606 1218 262144 735 1778 1 129 1591 1024 526 1043 256 86 1215 536870912 441 1947 8388608 720 1120 262144 566 1418 2097152...
output:
32815569966 34049201230 35262958893 36382166293 37477591545 38570338293 39648586499 40722326899 41791963551 42854276862 43785231196 44712215452 45519097750 46325542802 47130655418 47935175210 48735228326 49532251054 50304965454 51042325160 51747820310 52423889489 53094716245 53739413254 54345752382 ...
result:
ok 2000 numbers
Test #33:
score: 0
Accepted
time: 11ms
memory: 98100kb
input:
2000 2000 457 1664 524288 815 1742 8192 1106 1912 131072 989 1311 33554432 1174 1324 2 1151 1513 64 1346 1438 1024 890 1923 4 347 642 524288 1512 1900 32 244 297 67108864 490 1298 8388608 675 1793 128 287 1822 16 1690 1950 33554432 130 292 1024 1368 1712 512 611 949 16384 525 1282 1048576 864 1675 3...
output:
37484844800 38961174198 40202688182 41347995318 42488177101 43562035828 44635777908 45709502976 46774824672 47808703312 48676781551 49486806703 50293970348 51099865004 51905532118 52710838478 53516144466 54320234321 55116496441 55895597289 56658935783 57380157981 58085835871 58756954909 59427118493 ...
result:
ok 2001 numbers
Test #34:
score: 0
Accepted
time: 29ms
memory: 97988kb
input:
1999 1999 254 865 462237029 4 254 843431891 254 1415 11343807 254 749 296978536 254 379 170243393 254 1812 895194997 254 772 646926338 254 1783 95720864 254 1624 977470728 254 738 606456673 254 1804 808753625 254 1305 662341811 254 1103 793298257 254 346 64166919 254 1224 309310390 254 1277 13804658...
output:
1998451868 2997111472 3995665498 4993152167 5989482360 6985390510 7981036315 8976567267 9971908313 10966809174 11960921431 12953339365 13945502249 14937321010 15928820469 16920242511 17911435243 18901300971 19890914598 20880310011 21869697739 22858944715 23847053485 24834565866 25821725122 268084854...
result:
ok 2000 numbers
Test #35:
score: 0
Accepted
time: 23ms
memory: 98112kb
input:
2000 2000 176 531 102142910 211 531 388129165 531 1059 620150505 531 978 779832879 531 905 634815854 531 1186 418299985 223 531 401799347 531 1870 876075812 531 1211 675037357 531 1290 734722948 531 797 938505893 531 543 863818843 498 531 930705471 531 1423 99136835 531 704 747744439 531 677 5865214...
output:
1996428714 2994340292 3992215504 4989685772 5986977410 6981759736 7976043147 8969970402 9963869690 10957671177 11951459222 12945048293 13937793854 14930461244 15922637456 16914421046 17905081455 18895712962 19886235326 20876343193 21866100999 22855619353 23841266143 24826709290 25811949182 267970982...
result:
ok 2001 numbers
Test #36:
score: 0
Accepted
time: 31ms
memory: 98052kb
input:
1999 1999 504 1377 128 41 1377 2097152 1377 1433 1024 1377 1453 1048576 394 1377 536870912 643 1377 2097152 294 1377 16 95 1377 16777216 1377 1733 536870912 1377 1853 128 1377 1865 2048 1205 1377 32 639 1377 128 1377 1653 524288 1103 1377 32768 1377 1919 1 234 1377 4096 514 1377 64 681 1377 524288 1...
output:
1073741824 1610612736 2147483648 2684354560 3221225472 3758096384 4294967296 4831838208 5368709120 5905580032 6442450944 6979321856 7516192768 8053063680 8589934592 9126805504 9663676416 10200547328 10737418240 11274289152 11811160064 12348030976 12884901888 13421772800 13958643712 14495514624 15032...
result:
ok 2000 numbers
Test #37:
score: 0
Accepted
time: 23ms
memory: 98068kb
input:
2000 2000 1538 1887 8192 982 1538 32 1538 1583 262144 1214 1538 131072 1538 1645 8388608 1538 1748 131072 1379 1538 32 426 1538 65536 754 1538 512 1513 1538 8 550 1538 4194304 247 1538 16777216 787 1538 32 1538 1558 268435456 1333 1538 4194304 1538 1607 536870912 1538 1815 65536 1489 1538 16 60 1538...
output:
1073741824 1610612736 2147483648 2684354560 3221225472 3758096384 4294967296 4831838208 5368709120 5905580032 6442450944 6979321856 7516192768 8053063680 8589934592 9126805504 9663676416 10200547328 10737418240 11274289152 11811160064 12348030976 12884901888 13421772800 13958643712 14495514624 15032...
result:
ok 2001 numbers
Test #38:
score: 0
Accepted
time: 21ms
memory: 98232kb
input:
2000 2000 995 1391 883019336 622 1682 306942228 199 812 285161972 272 1650 365338680 1002 1586 87491881 649 1540 262270729 831 1813 737785704 1084 1901 981549490 534 1872 60792600 24 1065 567978318 727 1902 286477739 1616 1661 249676974 1629 1746 433053695 567 1635 362417497 508 1265 222289670 861 1...
output:
797999502390 800592472635 803157728774 805596924259 807968785876 810254006035 812535235907 814768286507 816913172262 819027346609 821133647881 823147306398 825124988183 827026832002 828903168608 830766637436 832602061080 834394521127 836158455604 837870467773 839503905969 841125008294 842743633687 8...
result:
ok 2001 numbers
Test #39:
score: 0
Accepted
time: 12ms
memory: 98120kb
input:
2000 2000 511 1504 612610179 143 378 547438068 858 1632 439130261 1477 1633 353499649 796 1296 990619868 625 791 593337014 811 1755 825066118 774 1381 966420612 574 1123 334313008 405 450 929257922 153 1659 398565475 934 1061 775797970 1004 1680 987606114 4 69 727062145 200 1271 672106274 325 1326 9...
output:
206013169976 221766219581 237174097583 252330651561 267189225334 281939111515 296315838565 310349788165 324183660459 337980623976 351172576539 364231725969 377261140193 390282474824 403181995034 414391354232 425520718904 436643500265 447510988649 458135388897 468560116674 478837964147 488884809284 4...
result:
ok 2001 numbers
Test #40:
score: 0
Accepted
time: 7ms
memory: 98068kb
input:
2000 2000 164 1578 42584803 24 628 51768345 141 408 724759728 817 1135 820795127 872 1302 728668452 1377 1531 360827901 75 1117 516321547 931 1228 923273639 222 659 904856926 421 1317 681848192 740 1655 987097304 272 1466 354195927 453 1190 820063431 1271 1406 498643123 1029 1797 889538343 75 230 72...
output:
137022393756 184001540585 211747169305 238399550657 263009345290 287128977446 309865681790 331337584562 352402803972 373314042523 392710089573 411761606943 429435467782 446667955020 463734893883 479383467634 494347745259 509003767019 523591184622 537781945594 551797050434 565121643898 578428746940 5...
result:
ok 2001 numbers
Test #41:
score: 0
Accepted
time: 16ms
memory: 98168kb
input:
2000 2000 995 1391 32768 622 1682 131072 199 812 2048 272 1650 524288 1002 1586 1 649 1540 256 831 1813 8388608 1084 1901 524288 534 1872 512 24 1065 128 727 1902 262144 1616 1661 8192 1629 1746 16384 567 1635 67108864 508 1265 536870912 861 1159 16 1515 1548 32 728 1410 8192 505 1931 16384 1296 196...
output:
52024911923 53072336923 54029171685 54901570517 55706876885 56433987961 57130870155 57700509285 58268799286 58805735734 59257114550 59609100196 59960415992 60275223254 60576148184 60845576969 61114519240 61382954952 61651390408 61818946488 61984621432 62119887720 62254629224 62388912616 62523130376 ...
result:
ok 2001 numbers
Test #42:
score: 0
Accepted
time: 8ms
memory: 98024kb
input:
2000 2000 511 1504 268435456 143 378 131072 858 1632 1 1477 1633 262144 796 1296 131072 625 791 8192 811 1755 134217728 774 1381 2 574 1123 128 405 450 2048 153 1659 16 934 1061 524288 1004 1680 8388608 4 69 16 200 1271 8192 325 1326 256 67 1518 4194304 570 1213 4194304 199 445 262144 121 655 104857...
output:
19224809596 21712093548 23944666988 26109038764 28249475967 30085052343 31864830529 33516675470 35120086241 36660146884 38171213013 39615384535 40916990181 42145960848 43289687039 44432890281 45556455806 46673486358 47769277242 48864613314 49944687732 51018429684 52010987412 52976450115 53938293220 ...
result:
ok 2001 numbers
Test #43:
score: 0
Accepted
time: 16ms
memory: 98072kb
input:
2000 2000 164 1578 4096 24 628 16384 141 408 131072 817 1135 67108864 872 1302 2097152 1377 1531 1 75 1117 64 931 1228 268435456 222 659 32768 421 1317 2 740 1655 8192 272 1466 65536 453 1190 1048576 1271 1406 4096 1029 1797 4194304 75 230 268435456 108 1452 2048 980 1489 2097152 381 508 32 80 552 4...
output:
9694755959 13148873418 16217351510 19284188089 21839638271 24196112415 26401427026 28388739104 30368317764 32083075010 33649463172 35195254676 36739281828 38182382483 39541096704 40893288660 42184711532 43474895073 44759933034 46040299083 47278110357 48491003476 49653643964 50803492684 51926062221 5...
result:
ok 2001 numbers
Test #44:
score: 0
Accepted
time: 25ms
memory: 97948kb
input:
2000 2000 1148 1391 883019336 622 1682 306942228 812 1148 285161972 1148 1650 365338680 1002 1148 87491881 1148 1540 262270729 831 1148 737785704 1084 1148 981549490 534 1148 60792600 1065 1148 567978318 727 1148 286477739 1616 1661 249676974 1148 1629 433053695 1148 1635 362417497 1148 1265 2222896...
output:
6187710486 9087948963 11609172278 14088311850 16414355916 18681380510 20942592971 23162711997 25363717559 27559559329 29717124899 31854382730 33972551273 36024052477 38037525235 40045637708 42020943778 43987635904 45922218697 47849557736 49764438133 51672415541 53553073773 55412693995 57266298086 59...
result:
ok 2001 numbers
Test #45:
score: 0
Accepted
time: 8ms
memory: 97984kb
input:
2000 2000 511 1263 612610179 143 378 547438068 858 1632 439130261 1263 1633 353499649 796 1296 990619868 791 1263 593337014 811 1755 825066118 774 1381 966420612 1123 1263 334313008 405 450 929257922 153 1659 398565475 934 1061 775797970 1004 1680 987606114 4 69 727062145 200 1271 672106274 325 1326...
output:
22953228449 33835809247 44230109331 54359508008 64477443663 74185408437 83840280201 93383185493 102203223470 111022797313 119721741692 128355848147 136677707765 144808297928 152880804450 160804900085 168640699914 176382564860 184103255514 191190424422 198251418056 205289474869 212324754492 219206443...
result:
ok 2001 numbers
Test #46:
score: 0
Accepted
time: 17ms
memory: 98036kb
input:
2000 2000 164 1578 42584803 24 628 51768345 141 1836 724759728 817 1135 820795127 872 1302 728668452 1377 1531 360827901 75 1117 516321547 931 1228 923273639 222 659 904856926 421 1317 681848192 740 1655 987097304 272 1466 354195927 453 1190 820063431 1271 1406 498643123 1797 1836 889538343 75 230 7...
output:
51547753054 68958666148 85676578195 102084739217 117602695048 132752803563 147599871318 162330838606 176372671058 190073988178 203613435593 216439242363 228545775944 240287333588 250898161475 261381780325 271761069430 282021414860 292225532323 302142502328 312028503550 321122785795 330133643383 3390...
result:
ok 2001 numbers
Test #47:
score: 0
Accepted
time: 27ms
memory: 97988kb
input:
2000 2000 1148 1391 32768 622 1682 131072 812 1148 2048 1148 1650 524288 1002 1148 1 1148 1540 256 831 1148 8388608 1084 1148 524288 534 1148 512 1065 1148 128 727 1148 262144 1616 1661 8192 1148 1629 16384 1148 1635 67108864 1148 1265 536870912 861 1159 16 1148 1515 32 728 1148 8192 505 1148 16384 ...
output:
1879048192 2684354560 3355705344 3968073728 4513333248 5054398464 5595463680 6136528896 6677594112 7215513600 7752909056 8289845504 8826765568 9363645698 9900524802 10437396226 10974267394 11511138322 12048009250 12584880162 13121751074 13658621986 14195492898 14732363810 15269234722 15806105634 163...
result:
ok 2001 numbers
Test #48:
score: 0
Accepted
time: 12ms
memory: 98032kb
input:
2000 2000 511 1263 268435456 143 378 131072 858 1632 1 1263 1633 262144 796 1296 131072 791 1263 8192 811 1755 134217728 774 1381 2 1123 1263 128 405 450 2048 153 1659 16 934 1061 524288 1004 1680 8388608 4 69 16 200 1271 8192 325 1326 256 67 1518 4194304 570 1213 4194304 199 445 262144 121 655 1048...
output:
3040024192 4382468000 5684964349 6911389353 8107815593 9253483323 10398245351 11522318823 12634867175 13609060327 14567831545 15524149529 16413347610 17294151451 18168673179 19006619155 19838480227 20661624683 21476074159 22289791791 23095626560 23900949824 24706264384 25463558619 26204902981 269064...
result:
ok 2001 numbers
Test #49:
score: 0
Accepted
time: 23ms
memory: 98056kb
input:
2000 2000 164 1578 4096 24 628 16384 141 1836 131072 817 1135 67108864 872 1302 2097152 1377 1531 1 75 1117 64 931 1228 268435456 222 659 32768 421 1317 2 740 1655 8192 272 1466 65536 453 1190 1048576 1271 1406 4096 1797 1836 4194304 75 230 268435456 108 1452 2048 980 1489 2097152 381 508 32 80 552 ...
output:
3616190424 5344318023 6971848596 8522733996 10036028604 11507758879 12888412067 14239028134 15575476685 16904141040 18087618954 19245250994 20376296965 21495467371 22575500779 23649608179 24675315115 25695406266 26702042298 27658872026 28599267713 29503309601 30376417989 31199600461 32010316333 3281...
result:
ok 2001 numbers
Test #50:
score: 0
Accepted
time: 0ms
memory: 3648kb
input:
2 0 1 2 1
output:
1
result:
ok 1 number(s): "1"
Test #51:
score: 0
Accepted
time: 0ms
memory: 3668kb
input:
2 0 1 2 1000000000
output:
1000000000
result:
ok 1 number(s): "1000000000"
Test #52:
score: 0
Accepted
time: 11ms
memory: 98108kb
input:
2000 2000 663 798 1 1305 1831 1 1521 1793 1 881 1192 1 1602 1861 1 727 1623 1 595 1059 1 1004 1014 1 1090 1173 1 1122 1655 1 147 1773 1 549 1598 1 469 1856 1 400 1845 1 557 1647 1 23 1914 1 745 1712 1 1037 1981 1 854 1876 1 86 1854 1 132 655 1 1842 1908 1 842 1277 1 278 935 1 576 1007 1 809 1988 1 2...
output:
1999 1999 1999 1999 1999 1999 1999 1999 1999 1999 1999 1999 1999 1999 1999 1999 1999 1999 1999 1999 1999 1999 1999 1999 1999 1999 1999 1999 1999 1999 1999 1999 1999 1999 1999 1999 1999 1999 1999 1999 1999 1999 1999 1999 1999 1999 1999 1999 1999 1999 1999 1999 1999 1999 1999 1999 1999 1999 1999 1999 ...
result:
ok 2001 numbers
Test #53:
score: 0
Accepted
time: 16ms
memory: 98188kb
input:
2000 2000 457 930 1000000000 66 753 1000000000 1196 1285 1000000000 517 1194 1000000000 1018 1227 1000000000 1506 1872 1000000000 1140 1142 1000000000 722 1405 1000000000 261 426 1000000000 773 1784 1000000000 85 867 1000000000 1132 1218 1000000000 1074 1098 1000000000 294 1751 1000000000 86 1694 10...
output:
1999000000000 1999000000000 1999000000000 1999000000000 1999000000000 1999000000000 1999000000000 1999000000000 1999000000000 1999000000000 1999000000000 1999000000000 1999000000000 1999000000000 1999000000000 1999000000000 1999000000000 1999000000000 1999000000000 1999000000000 1999000000000 199900...
result:
ok 2001 numbers
Test #54:
score: 0
Accepted
time: 29ms
memory: 97988kb
input:
2000 2000 798 988 1 988 1305 1 988 1793 1 988 1192 1 988 1861 1 727 988 1 595 988 1 988 1014 1 988 1090 1 988 1655 1 988 1773 1 988 1598 1 988 1856 1 988 1845 1 988 1647 1 23 988 1 988 1712 1 988 1981 1 988 1876 1 988 1854 1 132 988 1 988 1908 1 988 1277 1 278 988 1 576 988 1 988 1988 1 222 988 1 98...
output:
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 10...
result:
ok 2001 numbers
Test #55:
score: 0
Accepted
time: 30ms
memory: 97984kb
input:
2000 2000 369 930 1000000000 66 369 1000000000 369 1285 1000000000 369 517 1000000000 369 1227 1000000000 369 1872 1000000000 369 1142 1000000000 369 722 1000000000 261 369 1000000000 369 773 1000000000 85 369 1000000000 369 1132 1000000000 369 1074 1000000000 369 1751 1000000000 369 1694 1000000000...
output:
2000000000 3000000000 4000000000 5000000000 6000000000 7000000000 8000000000 9000000000 10000000000 11000000000 12000000000 13000000000 14000000000 15000000000 16000000000 17000000000 18000000000 19000000000 20000000000 21000000000 22000000000 23000000000 24000000000 25000000000 26000000000 27000000...
result:
ok 2001 numbers
Test #56:
score: 0
Accepted
time: 11ms
memory: 98080kb
input:
2000 2000 855 1726 536870912 1109 1829 536870912 565 1180 536870912 658 820 536870912 118 1999 536870912 48 444 536870912 14 1163 536870912 159 272 536870912 50 927 536870912 560 1325 536870912 843 1102 536870912 159 1925 536870912 439 1663 536870912 590 1644 536870912 129 443 536870912 639 656 5368...
output:
62277025792 95563022336 120795955200 142270791680 161061273600 178778013696 193810399232 207769042944 221727686656 235149459456 248034361344 260382392320 271656681472 282930970624 293668388864 304405807104 314606354432 323733159936 332859965440 341449900032 349502963712 357556027392 365072220160 372...
result:
ok 2001 numbers
Test #57:
score: 0
Accepted
time: 13ms
memory: 98116kb
input:
2000 2000 799 1142 536870912 622 1790 536870912 374 1141 536870912 19 1563 536870912 1141 1875 536870912 366 1661 536870912 107 149 536870912 95 1526 536870912 683 1462 536870912 288 1671 536870912 1302 1409 536870912 1110 1702 536870912 438 1063 536870912 726 1175 536870912 283 809 536870912 218 16...
output:
67108864000 104152956928 133143986176 159987531776 179851755520 199179108352 214748364800 229780750336 242665652224 255013683200 267361714176 279172874240 290447163392 301184581632 311921999872 321585676288 330712481792 339839287296 348966092800 357556027392 366145961984 373662154752 381178347520 38...
result:
ok 2001 numbers