QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#191377#7532. Inspection (32 MB ML!)Days_of_Future_Past#AC ✓874ms32972kbC++141.5kb2023-09-29 22:22:262023-09-29 22:27:17

Judging History

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

  • [2023-09-29 22:27:17]
  • 管理员手动重测本题所有提交记录
  • 测评结果:AC
  • 用时:874ms
  • 内存:32972kb
  • [2023-09-29 22:22:27]
  • 评测
  • 测评结果:0
  • 用时:574ms
  • 内存:32744kb
  • [2023-09-29 22:22:26]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define all(x) ((x).begin()), ((x).end())
typedef long long LL;
const int N = 10001;
const int L = 101;
int a[N];
LL s[N];
LL dp[L][L][L];
unsigned char u[N][L][21];
int pw[5];
inline void renew(int i, int j, int d, LL v, unsigned char x) {
	if(v > dp[i % L][j][d]) {
		dp[i % L][j][d] = v;
		int shift = d % 5;
		int old = u[i][j][d / 5] / pw[shift] % 3;
		
		u[i][j][d / 5] += (x - old) * pw[shift];
	}
}
int main() {
	pw[0] = 1;
	for(int i = 1; i <= 4; i++) {
		pw[i] = pw[i - 1] * 3;	
	}
	int n, k[2], l[2];
	scanf("%d%d%d%d%d", &n, &k[0], &l[0], &k[1], &l[1]);
		
	for(int i = 1; i <= n; i++) {
		scanf("%d", &a[i]);
		s[i] = s[i - 1] + a[i];
		memset(dp[i % L], -1, sizeof(dp[i % L]));
		for(int j = 0; j <= k[0]; j++) {
			for(int d = 0; d <= k[1]; d++) {
				renew(i, j, d, dp[(i - 1) % L][j][d], 2);
				if(j > 0 && i >= l[0]) {
					renew(i, j, d, dp[(i - l[0]) % L][j - 1][d] + s[i] - s[i - l[0]], 0);
				}
				if(d > 0 && i >= l[1]) {
					renew(i, j, d, dp[(i - l[1]) % L][j][d - 1] + s[i] - s[i - l[1]], 1);
				}
			}
		}
	}
	printf("%lld\n", dp[n % L][k[0]][k[1]]);
	int j = k[0], d = k[1], i = n;
	vector<pair<int, int> > ans;
	while(i > 0) {
		int x = u[i][j][d / 5] / pw[d % 5] % 3;
		if(x == 2) {
			i--;
		}else {
			ans.pb({i - l[x] + 1, i});
			i -= l[x];
			if(x == 0) j--;
			else d--;
		}
	}
	reverse(all(ans));
	for(auto t : ans) printf("%d %d\n", t.fi - 1, t.se);
}

这程序好像有点Bug,我给组数据试试?

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 5876kb

input:

20 2 3 3 2
2 0 2 0 1 2 1 2 1 2 2 2 1 1 2 2 2 1 2 2

output:

22
4 6
6 8
9 12
14 17
18 20

result:

ok Sum = 22

Test #2:

score: 0
Accepted
time: 1ms
memory: 7944kb

input:

25 1 5 1 10
30 8 87 61 66 75 86 3 14 23 56 36 60 23 32 65 49 61 11 50 98 91 36 12 85

output:

933
2 7
15 25

result:

ok Sum = 933

Test #3:

score: 0
Accepted
time: 0ms
memory: 10072kb

input:

50 3 3 3 5
19 54 97 19 24 82 0 57 88 32 95 62 60 52 75 21 73 38 11 29 98 8 39 76 94 90 63 81 48 55 64 34 28 27 72 73 70 28 75 76 84 14 15 29 82 46 36 55 47 83

output:

1659
1 6
10 15
23 28
34 37
38 41
47 50

result:

ok Sum = 1659

Test #4:

score: 0
Accepted
time: 3ms
memory: 14300kb

input:

100 20 1 25 2
980 361 796 376 660 459 30 116 265 564 904 831 111 427 376 848 291 126 983 411 272 596 53 757 459 340 901 182 263 595 548 471 699 450 117 63 383 17 45 967 406 858 72 212 356 598 757 70 658 310 424 100 772 505 767 239 368 793 557 574 103 175 213 313 366 24 444 690 599 106 881 224 737 46...

output:

40914
0 2
2 4
4 6
8 10
10 12
13 15
15 17
18 20
20 22
23 25
25 27
28 30
30 32
32 34
36 37
39 41
41 42
44 46
46 47
48 50
50 51
52 54
54 55
56 58
58 60
63 65
66 68
68 69
70 71
72 74
77 79
79 81
82 83
83 84
84 85
86 87
87 88
88 89
90 91
91 92
92 93
93 94
94 95
97 98
99 100

result:

ok Sum = 40914

Test #5:

score: 0
Accepted
time: 0ms
memory: 14448kb

input:

1000 7 7 10 10
1098 8117 3620 2772 168 7954 2367 2555 47 6780 3543 6578 3279 429 4574 1131 7204 247 4804 7522 6613 7478 137 9519 6242 672 7201 7048 2841 643 1026 5669 7345 665 4017 5513 7648 3792 552 1340 1353 9905 9339 10000 9312 2808 6614 6770 1668 263 5684 6018 3876 6349 4838 1611 7457 4651 9362 ...

output:

1049739
41 48
71 81
137 144
224 234
237 244
416 426
447 457
495 502
533 540
564 574
726 733
780 790
790 800
800 810
853 863
866 873
885 895

result:

ok Sum = 1049739

Test #6:

score: 0
Accepted
time: 3ms
memory: 15840kb

input:

1000 7 10 10 7
53695 79826 1503 87231 62923 31244 10625 22269 95977 14286 52926 26157 12349 49600 35265 26137 54048 4755 54475 13155 9512 25806 1792 36386 20637 61485 89544 74519 14004 4832 93060 19351 19248 77550 40734 14551 99724 86255 58169 90083 53691 83779 23138 59055 41834 60111 97787 98800 16...

output:

10131389
36 43
95 102
127 137
153 160
169 176
319 326
417 424
457 464
483 493
551 561
671 681
712 722
734 741
750 760
866 873
906 913
959 969

result:

ok Sum = 10131389

Test #7:

score: 0
Accepted
time: 6ms
memory: 14656kb

input:

1000 7 10 10 7
93057610 710924099 580827171 60715974 384532870 756528732 562359414 145202285 179229408 423581217 543310781 95754641 572714046 457947805 387620778 446039199 722087216 330855752 41597945 214667069 471030194 335646123 720015214 433192031 619739684 30406982 425746122 278912619 250025810 ...

output:

124209579368
43 50
109 116
154 161
206 213
270 280
324 334
383 393
440 447
492 502
553 560
609 616
664 674
725 732
771 778
824 834
886 896
948 955

result:

ok Sum = 124209579368

Test #8:

score: 0
Accepted
time: 202ms
memory: 18420kb

input:

2500 100 3 100 2
586722388 143502248 757639496 194345846 160173739 444325268 726685809 361039702 83180112 837256396 852938945 829940826 162684143 545551394 177182736 198180433 555173381 554180339 720376882 120409332 784137984 879015312 829589977 851922739 782539525 571151054 679783685 66476620 75261...

output:

448825044909
9 12
21 24
35 38
48 51
66 69
81 83
92 94
102 105
112 115
124 126
132 134
142 145
154 157
167 169
176 179
194 196
204 206
218 221
238 241
248 250
260 263
274 276
285 288
297 300
311 313
319 322
333 335
345 348
360 363
375 377
387 390
400 403
413 415
427 430
440 442
449 452
462 465
479 48...

result:

ok Sum = 448825044909

Test #9:

score: 0
Accepted
time: 187ms
memory: 18308kb

input:

2500 100 1 100 2
506580579 18598994 158570651 92140602 204931167 125238374 193735280 480390656 238320671 501410287 109652340 372173815 849723954 686185146 193482349 512935256 266181939 214966900 186262701 40458136 375562990 232682341 348797580 103945336 528168007 542655652 84760522 310605342 3554292...

output:

228659470578
12 14
24 26
37 38
56 57
66 67
83 84
91 92
102 104
118 119
127 129
144 146
162 163
173 175
181 183
196 198
205 207
219 221
233 234
244 245
256 257
269 271
280 281
292 293
305 307
314 315
324 326
338 340
353 355
367 368
377 379
389 391
402 404
417 418
426 428
442 443
455 456
466 468
482 4...

result:

ok Sum = 228659470578

Test #10:

score: 0
Accepted
time: 575ms
memory: 32668kb

input:

10000 100 40 60 100
210601834 47568766 750147761 251433165 676015635 48516996 626067380 141883480 562333839 975031747 753949608 300842579 278874290 393865163 825543678 884778731 608448539 377043321 19748664 582551454 915743153 442944058 937791124 470897130 421754305 357086069 297720913 828065947 331...

output:

4976287468399
0 100
100 200
200 300
300 400
400 500
500 600
600 700
700 800
800 900
900 1000
1000 1100
1100 1200
1200 1300
1300 1400
1400 1500
1500 1600
1600 1700
1700 1800
1800 1900
1900 2000
2000 2100
2100 2200
2200 2300
2300 2400
2400 2500
2500 2600
2600 2700
2700 2800
2800 2900
2900 3000
3000 31...

result:

ok Sum = 4976287468399

Test #11:

score: 0
Accepted
time: 102ms
memory: 32960kb

input:

10000 100 10 10 100
78196436 111525982 24371452 44672392 15271589 12141238 156312464 48642620 68931850 9687917 159073457 121523191 66238800 81140940 21713665 183058648 87679917 58999220 114891129 3827818 130261400 12475933 134753117 19254749 59654129 173948145 72946791 47569495 48942111 123953340 18...

output:

1195874936581
62 162
222 232
290 300
368 468
522 532
615 625
713 813
895 995
1067 1167
1244 1254
1307 1317
1390 1400
1471 1481
1564 1574
1647 1747
1838 1848
1922 1932
1999 2099
2157 2167
2226 2326
2401 2411
2482 2582
2643 2743
2823 2833
2910 2920
3001 3011
3083 3093
3170 3180
3245 3255
3321 3331
340...

result:

ok Sum = 1195874936581

Test #12:

score: 0
Accepted
time: 94ms
memory: 32972kb

input:

10000 100 10 10 100
133100750 388247186 410963416 420373419 308871987 471797662 175731660 286406597 36953552 160758172 381720732 325151929 479871742 179639744 17938763 5392025 9614573 348711851 1747533 75869904 524212197 144962465 259221633 385429669 349643069 82228387 143189629 344549497 411671689 ...

output:

1569136515388
67 77
152 252
333 343
419 429
496 506
572 582
665 675
733 833
895 905
985 995
1064 1074
1132 1142
1211 1221
1291 1391
1472 1482
1552 1652
1727 1737
1811 1911
1987 2087
2157 2257
2336 2436
2516 2616
2674 2774
2851 2861
2941 2951
3020 3030
3094 3104
3182 3192
3266 3276
3343 3353
3430 344...

result:

ok Sum = 1569136515388

Test #13:

score: 0
Accepted
time: 98ms
memory: 32928kb

input:

10000 100 11 10 99
266219590 582607138 104170125 111693064 471847975 614054948 634538360 190517942 587001254 587896826 157884077 403631134 281946196 67575683 571945383 387039522 461381847 355272705 432189648 389509134 373183738 622754924 572426491 188058805 353162667 517775399 134966201 637625586 22...

output:

1721251957894
78 177
243 254
317 416
484 583
654 665
739 838
919 1018
1089 1188
1260 1271
1342 1353
1429 1440
1521 1532
1603 1614
1669 1768
1844 1943
2014 2113
2175 2186
2273 2284
2363 2462
2533 2544
2604 2615
2684 2695
2765 2776
2848 2859
2936 2947
3012 3023
3093 3104
3181 3192
3259 3270
3331 3342
...

result:

ok Sum = 1721251957894

Test #14:

score: 0
Accepted
time: 91ms
memory: 32660kb

input:

10000 99 11 9 99
243181648 504914286 367020788 478905412 232521521 70814995 338597393 386759362 440091865 136546164 324391981 244696110 121609707 442502983 409324829 259391833 425358067 46400552 392404441 293394849 193683518 295940949 271808701 283569087 272456399 135478947 183089002 472153231 29428...

output:

1487327844045
80 179
242 253
325 424
502 601
688 787
867 966
1042 1053
1119 1130
1198 1209
1291 1302
1387 1398
1470 1481
1561 1660
1725 1736
1814 1825
1891 1990
2057 2068
2142 2241
2308 2319
2401 2412
2491 2590
2667 2678
2739 2750
2820 2831
2905 2916
2980 2991
3047 3058
3128 3139
3201 3212
3298 3309...

result:

ok Sum = 1487327844045

Test #15:

score: 0
Accepted
time: 47ms
memory: 32748kb

input:

10000 11 90 9 99
296204389 875468235 61186171 333868749 300512589 469039565 944978905 308877688 308547790 351363006 731598597 345146821 111245209 755063414 732250592 914071837 817713667 922792837 567455843 689538220 807176477 672791754 870065440 384043055 662814612 198938128 642047246 835724728 5062...

output:

1795991721566
414 513
888 987
1400 1499
1863 1953
2377 2476
2877 2976
3360 3450
3821 3911
4293 4392
4762 4852
5249 5348
5729 5828
6206 6296
6695 6794
7188 7278
7702 7792
8180 8270
8647 8737
9074 9164
9535 9625

result:

ok Sum = 1795991721566

Test #16:

score: 0
Accepted
time: 577ms
memory: 32968kb

input:

10000 99 11 77 7
175624176 500797374 210478104 421636739 816732454 230191357 473712908 570881127 731628122 222444095 162070806 754300710 527270049 461886912 710046913 466886145 47949895 710943262 211541450 20958875 425303325 240923784 526481288 588855963 344981002 353952105 533049267 154335739 55384...

output:

1468329866149
63 74
130 137
186 197
237 248
306 317
359 366
428 439
484 495
553 560
607 618
651 658
703 714
766 777
830 841
889 896
946 953
1004 1015
1070 1077
1123 1130
1175 1182
1233 1244
1287 1294
1345 1356
1403 1414
1466 1473
1516 1527
1568 1579
1629 1640
1686 1693
1750 1757
1802 1809
1859 1866
...

result:

ok Sum = 1468329866149

Test #17:

score: 0
Accepted
time: 28ms
memory: 32972kb

input:

10000 64 4 1 64
184227009 223419887 55234124 282814870 232225030 148098504 25222274 237587424 35344903 28557038 149780426 247328502 176957733 235938355 26329150 246983111 74278214 259829323 75986100 207294935 136116924 56827859 235781201 123367502 192348717 146043278 202301366 238503793 277785128 55...

output:

208931583022
170 174
183 187
334 338
491 555
728 732
875 879
1016 1020
1188 1192
1347 1351
1488 1492
1658 1662
1816 1820
1960 1964
2100 2104
2237 2241
2547 2551
2706 2710
2844 2848
2960 2964
3106 3110
3254 3258
3399 3403
3559 3563
3724 3728
3860 3864
4018 4022
4174 4178
4325 4329
4455 4459
4594 4598...

result:

ok Sum = 208931583022

Test #18:

score: 0
Accepted
time: 171ms
memory: 32668kb

input:

10000 64 2 32 8
17028366 26657577 11830482 7942768 27985465 1463151 13680828 7811876 20653783 8672710 12766860 8355368 19193607 24575211 17410440 28306776 5936533 16621200 5723270 18800884 24047200 7759613 23874487 16617275 3394117 14960030 9163170 6584293 29154866 20767590 14643481 221726 17818160 ...

output:

201832986713
104 112
227 229
327 335
520 528
626 634
853 861
874 876
963 965
1082 1084
1169 1171
1184 1186
1284 1292
1396 1398
1489 1497
1587 1589
1685 1687
1719 1721
1780 1788
1872 1874
1963 1971
2063 2071
2172 2174
2287 2289
2379 2387
2399 2401
2495 2503
2601 2609
2704 2706
2768 2770
2891 2899
300...

result:

ok Sum = 201832986713

Test #19:

score: 0
Accepted
time: 42ms
memory: 32708kb

input:

10000 33 3 7 77
680127398 487293180 69807102 282613417 199496420 416324380 441185479 100242601 53984566 28871688 621009168 553827378 115223060 168795334 576197627 292353445 515842260 288494445 554232838 329899532 767743725 39622596 205646460 596936543 427654584 599764523 263758602 195539352 66215668...

output:

538431607282
231 308
547 624
823 900
1137 1214
1425 1502
1723 1800
1998 2075
2320 2323
2549 2552
2768 2771
3016 3019
3232 3235
3449 3452
3673 3676
3908 3911
4130 4133
4352 4355
4568 4571
4789 4792
5006 5009
5250 5253
5491 5494
5757 5760
5995 5998
6236 6239
6486 6489
6712 6715
6972 6975
7198 7201
741...

result:

ok Sum = 538431607282

Test #20:

score: 0
Accepted
time: 720ms
memory: 32680kb

input:

10000 100 3 100 7
73866769 240623368 48600658 114826141 45584467 58995081 236207380 180447859 158198314 141408874 46431288 77243514 304200986 328130822 192795011 239016366 136061450 8945689 1196553 326901317 319480592 301210461 54022584 225827314 186383554 112047614 321385368 991093101 331469653 128...

output:

663792707277
26 29
55 62
100 103
155 162
195 198
245 252
297 304
342 349
379 386
425 432
474 477
528 535
575 582
629 636
685 688
719 726
767 770
813 820
849 852
892 899
920 923
940 947
984 991
1048 1051
1093 1096
1137 1140
1181 1188
1227 1230
1280 1283
1342 1349
1393 1396
1447 1450
1498 1505
1548 15...

result:

ok Sum = 663792707277

Test #21:

score: 0
Accepted
time: 874ms
memory: 32668kb

input:

10000 100 33 100 17
300011900 136501190 478373601 44788196 353229685 232499012 9316078 252104394 352141005 630758080 985629645 231199283 502707492 821232146 297487462 57431189 28455956 64143311 10877926 602606248 179399194 519253364 363102823 686963609 637855517 734639871 934650836 773722128 3182454...

output:

3962202684955
23 40
59 92
119 136
166 183
215 248
269 302
331 364
383 416
435 452
474 491
521 554
582 599
624 641
671 688
721 738
765 798
817 834
847 880
904 921
944 961
985 1002
1030 1063
1094 1111
1144 1161
1183 1200
1228 1245
1272 1305
1325 1358
1386 1403
1423 1440
1469 1502
1530 1563
1582 1599
1...

result:

ok Sum = 3962202684955