QOJ.ac

QOJ

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

Judging History

你现在查看的是测评时间为 2023-09-29 22:22:27 的历史记录

  • [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);
}

详细

Test #1:

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

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: 9980kb

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: 0ms
memory: 13188kb

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: 6ms
memory: 14276kb

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: 6ms
memory: 14216kb

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: 7ms
memory: 14120kb

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: 206ms
memory: 18476kb

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: 199ms
memory: 18832kb

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: 574ms
memory: 32732kb

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: 105ms
memory: 32668kb

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: 99ms
memory: 32744kb

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: -100
Memory Limit Exceeded

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: