QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#191377 | #7532. Inspection (32 MB ML!) | Days_of_Future_Past# | AC ✓ | 574ms | 32744kb | C++14 | 1.5kb | 2023-09-29 22:22:26 | 2023-09-29 22:22:27 |
Judging History
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);
}
Details
Tip: Click on the bar to expand more detailed information
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 ...