QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#625441#6107. One Pathstrlen_s_AC ✓31ms98232kbC++172.1kb2024-10-09 19:20:102024-10-09 19:20:10

Judging History

你现在查看的是最新测评结果

  • [2024-10-09 19:20:10]
  • 评测
  • 测评结果:AC
  • 用时:31ms
  • 内存:98232kb
  • [2024-10-09 19:20:10]
  • 提交

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