QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #129291 | #3998. The Profiteer | training4usaco | AC ✓ | 328ms | 21304kb | C++17 | 2.3kb | 2023-07-22 14:06:05 | 2023-07-22 14:06:08 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN = 2e5 + 5;
int n, k, e;
int a[MAXN], b[MAXN], val[MAXN];
int ans[MAXN];
int dp[MAXN];
int dp2[MAXN];
void upd(int w, int v) {
for(int i = k; i >= w; --i) dp[i] = max(dp[i], dp[i - w] + v);
}
void upd2(int w, int v) {
for(int i = k; i >= w; --i) dp2[i] = max(dp2[i], dp2[i - w] + v);
}
bool check(int l, int r, int ql, int qr) {
for(int i = 0; i <= k; ++i) dp2[i] = dp[i];
for(int i = l; i <= r; ++i) {
if(ql <= i && i <= qr) upd2(b[i], val[i]);
else upd2(a[i], val[i]);
}
int sum = 0;
for(int i = 0; i <= k; ++i) sum += dp2[i];
return sum <= e * k;
}
void magic(int l, int r, int ql, int qr) {
if(l > r || ql > qr) return;
if(ql == qr) {
for(int i = l; i <= r; ++i) ans[i] = ql;
return;
}
vector<int> cur(k + 1);
for(int i = 0; i <= k; ++i) cur[i] = dp[i];
int mid = (l + r) / 2;
for(int i = l; i < mid; ++i) upd(a[i], val[i]);
for(int i = mid; i <= min(ql - 1, r); ++i) upd(b[i], val[i]);
int nl = max(mid, ql), nr = qr;
while(nl <= nr) {
int nmid = (nl + nr) / 2;
if(check(nl, nr, mid, nmid)) {
for(int i = nmid; i <= nr; ++i) upd(a[i], val[i]);
ans[mid] = nmid; nr = nmid - 1;
}
else {
for(int i = nl; i <= nmid; ++i) upd(b[i], val[i]);
nl = nmid + 1;
}
}
for(int i = 0; i <= k; ++i) dp[i] = cur[i];
for(int i = mid; i <= min(r, ql - 1); ++i) upd(b[i], val[i]);
for(int i = ans[mid] + 1; i <= qr; ++i) upd(a[i], val[i]);
magic(l, mid - 1, ql, ans[mid]);
for(int i = 0; i <= k; ++i) dp[i] = cur[i];
for(int i = l; i <= mid; ++i) upd(a[i], val[i]);
for(int i = max(r + 1, ql); i < ans[mid]; ++i) upd(b[i], val[i]);
magic(mid + 1, r, ans[mid], qr);
}
signed main() {
cin.tie(0)->sync_with_stdio(false);
cin >> n >> k >> e;
for(int i = 1; i <= n; ++i) cin >> val[i] >> a[i] >> b[i];
for(int i = 1; i <= n; ++i) ans[i] = n + 1;
magic(1, n, 1, n + 1);
int sum = 0;
for(int i = 1; i <= n; ++i) sum += (n - ans[i] + 1);
cout << sum << endl;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 9680kb
input:
4 5 3 3 2 4 1 2 3 2 1 2 3 1 3
output:
1
result:
ok single line: '1'
Test #2:
score: 0
Accepted
time: 2ms
memory: 9628kb
input:
4 5 4 3 2 4 1 2 3 2 1 2 3 1 3
output:
3
result:
ok single line: '3'
Test #3:
score: 0
Accepted
time: 2ms
memory: 9616kb
input:
4 5 5 3 2 4 1 2 3 2 1 2 3 1 3
output:
7
result:
ok single line: '7'
Test #4:
score: 0
Accepted
time: 310ms
memory: 10052kb
input:
200000 50 23333 2620 5 21 8192 17 34 6713 38 46 6687 13 42 390 9 13 4192 7 37 7898 17 21 1471 16 45 3579 22 40 9628 8 23 7164 28 45 3669 14 31 5549 29 35 4670 30 39 5811 15 20 4162 18 29 7590 29 41 7786 23 35 383 9 40 5576 39 46 5586 4 9 1110 14 33 8568 4 6 8548 39 42 9133 10 42 6679 22 39 8353 33 3...
output:
0
result:
ok single line: '0'
Test #5:
score: 0
Accepted
time: 300ms
memory: 11152kb
input:
200000 50 233332 8019 18 20 3111 27 40 2015 16 47 6491 17 18 1224 30 38 428 23 34 7521 4 41 7252 6 33 4121 32 45 4230 18 35 1605 21 42 9489 17 25 3704 35 45 6202 8 22 6493 1 5 3041 14 46 4509 23 43 9646 11 48 5294 19 27 3562 19 40 9408 30 47 1751 21 29 4053 4 27 5596 32 49 8609 13 29 1686 4 31 3588 ...
output:
17523021
result:
ok single line: '17523021'
Test #6:
score: 0
Accepted
time: 290ms
memory: 11096kb
input:
200000 50 2333331 7420 30 44 8652 22 28 5418 8 21 9825 3 8 4257 21 40 9962 6 16 3370 18 41 2192 37 41 231 8 18 7764 3 41 3455 9 18 1159 8 46 9775 9 42 4400 21 43 4593 10 22 712 7 22 2067 21 27 9618 9 35 8008 13 38 114 4 31 4503 39 49 4661 14 41 4837 15 35 1371 12 16 9568 21 48 8934 16 34 870 4 35 83...
output:
20000100000
result:
ok single line: '20000100000'
Test #7:
score: 0
Accepted
time: 328ms
memory: 11672kb
input:
200000 50 253330 4837 37 46 2436 11 48 2043 24 50 3544 27 40 1499 21 43 9009 36 46 9172 11 17 585 29 44 6379 4 28 6630 25 37 9230 24 35 5736 23 50 4324 34 50 4624 23 47 9933 3 12 577 12 18 4411 24 32 8750 42 48 4808 21 34 3904 7 17 5979 41 48 2838 29 40 8682 25 46 4026 11 19 8371 8 42 4550 6 24 1546...
output:
2513593675
result:
ok single line: '2513593675'
Test #8:
score: 0
Accepted
time: 307ms
memory: 10360kb
input:
200000 50 193334 8521 14 21 3902 5 6 2949 4 41 1034 10 36 6156 16 36 9432 35 37 3752 25 37 9668 5 9 3194 43 45 9849 1 26 1582 6 10 9920 20 50 994 34 50 9510 12 38 4513 18 31 6294 3 48 4949 9 18 2348 10 49 5492 19 46 2265 3 37 67 20 40 8752 1 5 4610 27 41 7344 27 39 7767 16 29 921 7 16 1853 23 44 936...
output:
1432887
result:
ok single line: '1432887'
Test #9:
score: 0
Accepted
time: 181ms
memory: 10420kb
input:
100000 100 304560 2347 27 64 3715 15 62 6005 16 86 9856 21 55 1347 5 89 9403 25 33 3889 36 74 554 18 95 5218 27 72 3282 2 68 4955 48 83 3478 7 36 3917 34 99 2117 24 41 9764 35 52 7991 81 94 8026 55 69 7755 27 44 3568 18 50 1968 36 57 7992 63 67 7760 4 55 6938 4 53 722 89 99 1111 47 66 5995 71 80 510...
output:
6114559
result:
ok single line: '6114559'
Test #10:
score: 0
Accepted
time: 183ms
memory: 9708kb
input:
100000 100 404561 3114 87 96 4983 68 99 4734 9 65 3721 49 79 7965 40 74 4463 33 81 731 7 61 9048 36 50 6891 40 68 4236 2 43 5436 6 45 1643 64 85 6889 5 95 5673 21 42 2119 57 70 2940 14 98 5620 59 67 8567 76 90 7543 81 99 5576 4 51 7281 4 100 2485 55 75 9357 6 45 4345 33 62 2261 7 26 2371 4 44 9758 5...
output:
29508633
result:
ok single line: '29508633'
Test #11:
score: 0
Accepted
time: 188ms
memory: 9936kb
input:
100000 100 454562 4294 4 37 7975 12 19 4648 1 83 674 41 84 8184 33 57 9088 56 79 2734 56 60 411 11 52 267 20 41 3503 75 86 6921 24 90 1255 49 90 1841 25 27 7767 86 97 9921 25 26 3063 23 44 9237 10 32 4991 7 87 969 36 100 5989 21 87 1420 45 73 780 7 26 6408 85 90 33 31 41 9767 36 89 7666 16 35 3725 1...
output:
160913569
result:
ok single line: '160913569'
Test #12:
score: 0
Accepted
time: 129ms
memory: 10172kb
input:
50000 200 604563 7628 31 102 3694 47 127 4931 101 187 332 7 146 800 131 143 6750 50 136 3718 88 108 5113 36 188 6565 16 49 7739 66 159 215 97 125 1184 90 150 6960 41 173 2281 18 66 3221 144 155 3431 12 162 4191 59 164 8530 28 30 2720 103 196 1176 171 194 2328 124 200 8209 62 114 2606 6 168 1201 120 ...
output:
97043020
result:
ok single line: '97043020'
Test #13:
score: 0
Accepted
time: 143ms
memory: 10040kb
input:
50000 200 804564 2147 132 170 2582 142 185 2492 29 44 4085 50 81 2749 40 115 7068 3 49 5096 72 127 2097 71 122 6697 130 145 6755 141 163 6197 66 130 3397 136 167 7546 71 156 7798 153 169 655 91 94 9498 62 117 7881 71 112 582 67 100 2382 6 189 7366 101 116 2254 56 138 4321 68 125 1601 44 54 2186 65 1...
output:
566251550
result:
ok single line: '566251550'
Test #14:
score: 0
Accepted
time: 147ms
memory: 9656kb
input:
50000 200 824565 2301 142 166 3523 60 153 3438 18 182 4052 42 116 6084 106 166 5687 45 55 2362 34 57 891 171 177 4412 18 49 3142 99 186 9489 86 103 7153 32 90 8357 35 115 6666 161 181 9346 160 196 6328 60 119 3756 16 135 990 130 150 4038 113 128 3608 69 127 8803 119 193 7508 100 141 2918 96 179 5466...
output:
718514472
result:
ok single line: '718514472'
Test #15:
score: 0
Accepted
time: 143ms
memory: 9784kb
input:
50000 200 844566 3943 49 169 1142 177 181 5370 77 91 9254 48 141 1986 87 196 8256 21 188 4440 116 174 6575 5 126 6139 8 67 5192 44 66 3795 51 60 2574 93 139 9861 46 164 3735 46 149 4388 19 46 3578 110 138 6011 25 99 9446 145 189 9215 22 156 9708 119 128 4207 28 172 1229 19 121 4672 161 174 938 35 60...
output:
832753831
result:
ok single line: '832753831'
Test #16:
score: 0
Accepted
time: 122ms
memory: 9756kb
input:
50000 200 864567 1496 192 200 501 22 137 8461 144 151 6841 56 92 4249 5 170 8990 100 155 8686 54 66 3745 144 175 406 127 179 8669 94 108 6146 141 187 1715 178 188 9270 20 160 1541 12 19 9499 66 132 2513 124 152 6228 83 126 8232 106 133 9816 101 197 7403 28 98 4128 14 113 2935 162 190 9541 78 166 773...
output:
1250025000
result:
ok single line: '1250025000'
Test #17:
score: 0
Accepted
time: 95ms
memory: 9692kb
input:
20000 500 604507 8220 251 441 473 267 330 7866 43 172 1675 178 390 7373 216 466 5691 122 274 4101 219 461 7195 406 475 3120 229 462 9594 164 276 8539 4 337 4490 98 498 6378 297 375 2771 40 144 5832 127 372 7877 6 438 9080 140 247 3343 56 354 4402 329 451 7275 56 90 8068 32 47 1412 143 373 9605 17 41...
output:
22551597
result:
ok single line: '22551597'
Test #18:
score: 0
Accepted
time: 99ms
memory: 9728kb
input:
20000 500 704517 6908 150 406 9324 73 113 9557 128 342 3522 265 344 5140 74 283 6988 397 456 8814 436 439 8944 74 400 9177 158 459 6200 105 230 2367 4 247 5138 402 427 9506 181 272 3341 94 396 8436 34 396 3890 195 466 2215 364 372 8343 159 489 7693 57 82 1961 43 74 3854 205 350 5171 38 87 9512 377 4...
output:
46171637
result:
ok single line: '46171637'
Test #19:
score: 0
Accepted
time: 99ms
memory: 9844kb
input:
20000 500 804527 694 70 142 6628 18 245 8865 27 483 472 22 297 5019 332 444 618 411 474 8356 336 483 2233 353 367 3244 193 322 4513 28 455 4447 52 243 7911 8 270 3402 49 469 6244 427 449 7769 27 359 8126 33 108 7584 314 358 6188 115 337 2092 38 154 6307 46 389 7366 34 362 4285 150 393 9307 399 419 6...
output:
90970591
result:
ok single line: '90970591'
Test #20:
score: 0
Accepted
time: 96ms
memory: 9756kb
input:
10000 1000 704537 6257 67 731 8667 640 807 7190 16 344 8470 336 963 5114 32 272 4196 825 946 8056 363 991 7445 616 873 242 237 944 2998 694 786 1256 105 229 3271 538 719 7616 451 687 8292 65 854 6622 407 883 4558 643 805 9402 240 572 1664 182 253 6327 702 851 6549 232 479 3798 22 490 8720 597 963 15...
output:
44558728
result:
ok single line: '44558728'
Test #21:
score: 0
Accepted
time: 79ms
memory: 9920kb
input:
5000 2000 404547 1199 130 149 2031 232 1571 8922 942 1218 7294 143 166 7867 364 666 5214 609 1185 785 618 1453 4296 1165 1731 7467 939 1711 4932 32 336 1804 1377 1750 6492 279 846 3487 361 516 7077 1668 1909 2759 781 1319 1519 574 1831 5072 389 971 7269 521 1155 2308 707 713 1947 288 930 2934 443 76...
output:
3355833
result:
ok single line: '3355833'
Test #22:
score: 0
Accepted
time: 53ms
memory: 9836kb
input:
3000 3000 204557 3644 409 2773 9860 1718 1833 6980 849 1708 5059 744 878 5394 1473 2309 6100 1424 2358 4621 338 2392 8682 781 1500 2734 822 1792 1935 562 1215 6772 454 750 8506 453 1765 3681 1742 2506 6915 387 1496 3963 1943 2004 6263 1859 2591 3124 334 897 3631 352 1380 1132 1075 1753 7719 1832 196...
output:
404256
result:
ok single line: '404256'
Test #23:
score: 0
Accepted
time: 54ms
memory: 9920kb
input:
3000 3000 254557 5040 794 2655 8982 113 2414 2507 796 1594 1127 224 1427 694 655 1184 3136 1607 2269 606 750 1453 7027 696 1263 5853 523 2414 4896 129 2589 7544 878 2295 689 368 1422 5719 1397 1848 3939 835 887 2854 550 738 7426 283 2732 4328 1468 1676 6199 657 1514 8612 1284 1601 6594 288 2356 9930...
output:
626919
result:
ok single line: '626919'
Test #24:
score: 0
Accepted
time: 70ms
memory: 9860kb
input:
3000 3000 304557 9819 663 846 4223 2500 2553 2955 2016 2896 9526 1334 1873 2184 985 1087 1539 1303 2638 6366 2141 2314 8445 329 2572 7882 1503 2075 5998 925 1904 779 1964 2148 2609 774 1142 7463 1613 1986 8926 819 1402 3880 1446 1669 7101 201 1722 8076 273 2570 8653 1484 2658 3424 2201 2591 7281 282...
output:
1789494
result:
ok single line: '1789494'
Test #25:
score: 0
Accepted
time: 68ms
memory: 9828kb
input:
3000 3000 354557 9782 185 1593 3837 2922 2949 8960 518 1539 3903 73 768 3087 2284 2848 4054 239 1071 8856 920 1389 9133 2053 2528 2062 1764 2649 1854 992 2275 6359 205 373 3649 1397 1419 6880 2285 2912 2055 1350 2453 318 1886 1971 4250 829 2565 313 1188 2713 3727 113 2141 3288 627 2569 2197 116 2099...
output:
2198841
result:
ok single line: '2198841'
Test #26:
score: 0
Accepted
time: 65ms
memory: 9832kb
input:
3000 3000 404557 708 802 2784 6640 109 1264 6684 46 1872 2837 1443 2707 587 1190 2330 6780 621 1708 2159 1522 1704 8738 1483 1908 238 137 516 3032 1739 2649 3675 1249 2777 1836 46 1902 1388 1713 2947 5627 476 1478 3073 812 1039 1235 2360 2589 9211 167 2441 8579 1740 2393 1982 461 2914 8369 865 925 8...
output:
3206289
result:
ok single line: '3206289'
Test #27:
score: 0
Accepted
time: 74ms
memory: 9932kb
input:
2000 5000 304567 3784 2499 5000 3491 2864 4941 3594 2101 3768 8110 1158 3663 1039 751 4924 333 80 2728 844 1083 4516 1940 63 3261 4414 1718 2352 4158 1027 3827 7048 1886 3090 7294 2842 3093 9489 1056 4955 5573 3166 4734 737 1959 3819 7890 2266 4309 7453 1680 4291 237 419 486 5602 495 1736 4968 487 4...
output:
1814585
result:
ok single line: '1814585'
Test #28:
score: 0
Accepted
time: 60ms
memory: 10404kb
input:
1000 10000 204577 1152 5103 9381 8782 268 5975 7743 6743 7323 8250 8412 8621 3987 7810 9955 9988 3263 5353 3267 1270 2302 9258 1791 8246 6156 5588 5865 3605 173 2370 6062 4685 6687 2097 6056 7346 7872 1131 1820 9835 5267 8695 6997 3397 9090 6233 6312 6664 361 309 743 3467 5699 8922 7766 670 7035 815...
output:
87842
result:
ok single line: '87842'
Test #29:
score: 0
Accepted
time: 49ms
memory: 11124kb
input:
500 20000 104587 964 4142 16635 6646 6532 10065 7296 7455 19855 4317 10262 10674 737 10824 12615 1947 5010 6953 2191 4137 18435 692 5757 13061 6052 14796 15895 4903 1335 13698 3006 927 7492 8096 952 4912 8212 10091 14249 9475 13819 14844 6903 3421 10365 2033 15662 17575 2061 4732 13496 1339 5005 152...
output:
38003
result:
ok single line: '38003'
Test #30:
score: 0
Accepted
time: 51ms
memory: 12856kb
input:
200 50000 74597 9588 27711 49855 5798 13401 35454 3163 37425 43074 1300 14772 49588 5445 8585 44770 3393 18689 43728 7747 5528 32127 1335 16928 45939 2038 10120 35057 7556 4277 19641 5989 2879 46380 8818 29554 36714 8791 2348 40820 9264 29592 34761 2033 826 29568 2253 40270 48103 6498 3469 22981 103...
output:
4693
result:
ok single line: '4693'
Test #31:
score: 0
Accepted
time: 67ms
memory: 15512kb
input:
100 100000 64067 3830 10209 47413 2236 11577 63433 602 12486 15366 9978 39578 67766 4732 80805 93353 1222 64481 86851 4368 29603 38059 6669 13473 73241 6857 33194 50911 6248 37920 39054 9414 10801 73316 6527 11781 63154 3570 53755 56008 5385 7820 34323 4335 37647 92580 8397 27180 82736 2773 71697 89...
output:
5050
result:
ok single line: '5050'
Test #32:
score: 0
Accepted
time: 41ms
memory: 20268kb
input:
50 200000 2167 5125 2778 70281 7973 49883 131314 6688 60715 63660 1842 64990 87433 2170 44234 140368 7454 5352 106136 740 49479 73311 683 74708 188982 1814 74591 148654 9219 36677 158650 5554 4211 170022 6362 48921 68439 7925 6840 88248 6590 38020 186698 3803 24350 76742 6265 54217 119088 1303 58245...
output:
0
result:
ok single line: '0'
Test #33:
score: 0
Accepted
time: 35ms
memory: 20256kb
input:
50 200000 4167 6609 143489 170762 434 28498 122523 1227 39445 153286 7182 67865 156238 2850 88324 174863 9332 43804 102485 8834 55181 123990 1101 80491 164065 6758 104936 132629 5497 18085 184894 2385 90449 193119 5840 22417 46690 5918 9637 188692 1496 154233 158153 3819 101861 121123 9746 55797 180...
output:
0
result:
ok single line: '0'
Test #34:
score: 0
Accepted
time: 37ms
memory: 18956kb
input:
50 200000 7167 7703 52615 124671 9171 112234 122718 4898 73136 156936 44 17394 39016 2675 15166 116007 3571 26765 197777 4250 118182 187213 2203 102983 191342 7337 92218 110455 8602 87335 154991 8615 57163 114174 1746 23030 163737 3675 13164 87869 5748 12601 113569 7713 9949 20072 5369 99739 161123 ...
output:
0
result:
ok single line: '0'
Test #35:
score: 0
Accepted
time: 25ms
memory: 21208kb
input:
50 200000 10167 8075 59281 59771 7041 117846 144814 6023 117104 132757 5542 71215 145103 2826 59190 86575 6164 70537 156429 4401 37851 54386 4588 50954 69363 8340 155681 170235 8904 89500 124427 6087 42177 151934 1285 58299 111323 1944 147771 183280 7506 41632 89665 5947 39825 144201 7518 94117 1937...
output:
21
result:
ok single line: '21'
Test #36:
score: 0
Accepted
time: 36ms
memory: 20008kb
input:
50 200000 14167 8475 123768 166527 850 29097 94804 5234 3747 28169 4356 44647 182942 1534 34124 119082 568 41249 169003 5523 25967 179160 4199 125909 195567 3709 83310 107375 3 88826 154545 9018 120591 150466 5795 2365 79805 4236 114610 142555 1315 36306 192017 9097 139543 181116 4774 46101 62074 44...
output:
4
result:
ok single line: '4'
Test #37:
score: 0
Accepted
time: 41ms
memory: 20456kb
input:
50 200000 24267 860 56050 101280 9482 12523 82739 7002 96274 167332 1735 31033 120671 1444 20893 177228 9069 79034 104342 4663 4108 175891 9156 11549 94621 7680 68395 163471 4626 62487 139183 9789 84524 165403 3513 162012 169007 1202 78679 176824 5813 73637 158062 4403 2046 125475 2770 122228 168401...
output:
62
result:
ok single line: '62'
Test #38:
score: 0
Accepted
time: 49ms
memory: 21304kb
input:
50 200000 34367 541 155629 179137 4059 22479 137541 6141 159107 188389 278 19063 23156 5135 17960 76747 1840 58827 190124 2608 171542 171885 8786 49163 190480 6538 69653 102189 1768 100965 190700 1403 10354 86777 3623 86885 89463 5140 58840 86043 329 56549 57262 5265 103074 120836 8925 2951 162804 4...
output:
330
result:
ok single line: '330'
Test #39:
score: 0
Accepted
time: 58ms
memory: 20404kb
input:
50 200000 44467 223 31016 113891 7147 175538 192343 7660 42812 105830 209 102077 129868 5152 94434 191559 8388 87639 117730 1485 28204 132552 8809 170745 186947 2341 93961 124618 23 39919 45097 3256 52611 124108 8333 143322 151453 6180 123405 124163 53 88094 151622 9742 10524 197180 3380 164772 1675...
output:
1002
result:
ok single line: '1002'
Test #40:
score: 0
Accepted
time: 72ms
memory: 21036kb
input:
50 200000 54567 2608 163298 191748 1336 151724 199218 7583 75268 132388 5708 20567 51030 1886 53039 192285 2434 4767 31740 6958 22347 133016 1841 10426 42371 4880 117264 198594 4871 38818 130913 982 83057 178873 7248 89559 151763 7588 133893 153628 7632 33222 98881 9013 169605 170072 1552 66387 8257...
output:
1275
result:
ok single line: '1275'
Test #41:
score: 0
Accepted
time: 93ms
memory: 20236kb
input:
50 200000 124567 8046 1673 12320 4527 7633 8347 6065 8788 17721 50 14367 16764 1647 6095 15154 7163 3247 10494 1414 2538 13294 4240 10028 18944 8246 9681 11495 589 11293 13298 823 6913 9049 7983 5440 14413 8809 3631 12404 1209 4002 14933 2872 5832 19658 1125 13153 17742 7418 15711 17634 3361 8078 13...
output:
1109
result:
ok single line: '1109'
Test #42:
score: 0
Accepted
time: 106ms
memory: 10344kb
input:
1000 10000 404577 8343 397 497 7095 129 853 4996 483 714 540 4 102 908 617 926 4941 119 137 700 99 134 9050 907 983 7465 41 387 4598 355 797 9844 116 664 2758 37 392 2373 134 220 2582 52 842 1695 142 964 2713 257 673 5383 256 593 5861 379 630 8529 342 440 959 92 197 7169 333 496 1403 30 797 3521 72 ...
output:
33293
result:
ok single line: '33293'
Test #43:
score: 0
Accepted
time: 106ms
memory: 9840kb
input:
3000 3000 354557 667 39 264 3290 162 213 4403 20 82 8045 204 266 2342 18 220 8238 70 120 2250 26 253 141 212 237 5243 26 70 6561 74 159 9703 135 163 6195 69 270 2266 34 73 587 33 231 6431 104 252 5090 171 280 5682 131 134 2588 24 235 4331 100 252 425 66 227 5629 241 291 2241 132 254 9779 56 145 8481...
output:
6561
result:
ok single line: '6561'
Test #44:
score: 0
Accepted
time: 162ms
memory: 9776kb
input:
20000 500 804527 8691 2 48 4859 5 38 4936 2 7 9992 7 23 8808 21 37 3404 22 27 6721 44 47 2131 3 24 6770 34 39 7363 4 32 5975 4 39 6400 3 15 7312 1 48 811 32 40 7166 6 9 1480 5 39 5679 3 40 1423 44 46 6806 34 43 4842 20 47 1077 11 36 5635 36 46 972 3 23 751 11 48 7863 17 34 6453 18 43 469 5 29 7342 1...
output:
798093
result:
ok single line: '798093'
Test #45:
score: 0
Accepted
time: 219ms
memory: 9752kb
input:
100000 100 404561 5263 2 10 8739 6 7 4158 4 9 5983 4 8 4830 4 7 8523 6 8 8669 5 7 143 3 9 4474 1 4 8342 1 5 7599 9 10 7289 7 10 7332 2 3 7176 1 8 6669 5 6 4666 8 9 4037 1 6 952 8 9 1605 1 4 208 1 10 7461 2 9 6393 3 5 3449 1 7 8153 2 4 3293 7 9 4766 1 5 9760 4 6 6528 2 4 9026 8 10 2665 5 7 4063 2 6 5...
output:
259833
result:
ok single line: '259833'
Test #46:
score: 0
Accepted
time: 259ms
memory: 11028kb
input:
200000 50 253330 1631 1 3 5059 2 3 3034 2 3 2357 1 3 5126 1 3 5075 1 3 5402 1 4 2726 3 4 1293 2 4 4754 2 3 4080 3 5 6605 2 4 5720 1 5 8507 2 5 1701 2 5 2164 2 5 7377 3 4 4295 1 2 610 1 4 675 2 5 8173 4 5 928 2 3 5631 3 5 3207 3 5 9824 2 3 7127 3 5 4797 3 5 7650 2 5 3751 1 3 9051 1 5 490 1 4 661 1 2 ...
output:
23812305
result:
ok single line: '23812305'
Test #47:
score: 0
Accepted
time: 108ms
memory: 9796kb
input:
3000 3000 1333333 9980 3 5 9918 4 5 9937 2 5 9913 2 5 9916 4 5 9915 3 5 9930 3 4 9918 4 5 9954 1 5 9948 2 4 9930 3 4 9933 4 5 9921 2 4 9941 1 5 9978 2 3 9964 3 4 9936 4 5 9933 1 3 9914 4 5 9910 1 5 9988 1 2 9982 1 3 9907 4 5 9932 3 4 9918 1 2 9910 1 2 9951 1 5 9921 3 5 9989 2 3 9920 1 4 9909 2 4 996...
output:
0
result:
ok single line: '0'
Test #48:
score: 0
Accepted
time: 109ms
memory: 9796kb
input:
3000 3000 2333333 9955 1 2 9910 1 2 9928 1 3 9993 2 4 9969 1 3 9901 3 5 9916 2 3 9920 1 5 9972 1 5 9975 2 3 9992 3 5 9958 2 4 9917 1 3 9977 3 4 9909 1 2 9914 4 5 9959 1 5 9962 3 4 9999 1 4 9960 1 2 9999 2 3 9952 1 2 9972 1 5 9901 4 5 9974 2 3 9914 4 5 9956 1 5 9941 1 2 9916 1 3 9990 2 5 9935 2 3 992...
output:
0
result:
ok single line: '0'
Test #49:
score: 0
Accepted
time: 99ms
memory: 9856kb
input:
3000 3000 233333333 9978 1 3 9962 1 2 9920 2 4 9929 3 4 9925 4 5 9941 3 5 9980 2 4 9909 3 5 9914 1 2 9958 1 5 9974 1 4 9922 2 4 9945 2 3 9960 2 4 9909 1 2 9999 2 4 9949 4 5 9990 1 4 9992 3 5 9987 3 5 9915 3 4 9933 4 5 9963 1 3 9961 4 5 9988 1 3 9956 1 2 9990 1 4 9955 1 2 9976 1 3 9956 1 2 9912 3 5 9...
output:
4501500
result:
ok single line: '4501500'
Test #50:
score: 0
Accepted
time: 96ms
memory: 9812kb
input:
3000 3000 1000000000 9932 1 2 9941 2 5 9986 3 4 9987 4 5 9961 1 4 9992 3 4 9902 2 4 9938 1 2 9951 1 3 9994 2 3 9965 1 3 9950 2 4 9963 3 5 9963 3 5 9963 2 4 9901 2 5 9948 3 4 9953 2 4 9942 2 3 9902 2 3 9902 1 2 9973 2 3 9974 2 3 9931 3 5 9977 3 5 9925 2 4 9912 4 5 9969 2 3 9976 2 5 9907 1 5 9947 4 5 ...
output:
4501500
result:
ok single line: '4501500'
Test #51:
score: 0
Accepted
time: 261ms
memory: 10964kb
input:
200000 50 253150 3417 3 5 5703 2 5 1259 2 3 1128 1 2 6393 2 5 6923 2 3 2652 1 3 912 4 5 1512 2 4 3657 2 5 5010 1 2 3115 3 5 9910 3 4 7418 1 5 4118 2 5 8356 2 4 5041 2 5 1980 1 4 8462 3 4 9374 1 4 6072 4 5 9040 1 5 7581 1 2 9486 1 3 505 2 4 6573 1 3 9417 2 4 4210 1 4 1401 4 5 8497 2 4 4144 3 4 4982 1...
output:
12338351
result:
ok single line: '12338351'
Test #52:
score: 0
Accepted
time: 296ms
memory: 10124kb
input:
200000 50 253021 4305 9 12 1502 7 9 379 10 12 7209 4 10 6665 1 10 3190 1 2 303 1 12 8278 1 9 7731 2 10 3271 6 7 5207 7 10 3712 1 5 7176 1 9 1625 9 12 244 3 7 6187 7 11 7212 5 8 5651 6 7 8764 5 11 444 4 5 52 8 9 3902 10 12 9185 7 12 2490 2 6 1216 2 10 2532 1 8 2914 6 11 1448 2 10 7678 5 6 4809 2 9 30...
output:
73081104
result:
ok single line: '73081104'
Test #53:
score: 0
Accepted
time: 289ms
memory: 10716kb
input:
200000 50 250749 4324 5 9 1113 5 7 6156 5 9 954 6 9 7962 4 5 1518 7 9 3843 2 4 2282 1 8 3343 1 6 758 5 7 3300 3 6 8241 3 9 8236 4 9 9044 5 6 7418 5 6 5634 1 9 9846 6 9 2489 3 8 3675 3 8 5248 3 4 2009 5 9 3478 1 6 792 2 3 279 6 9 6283 3 7 4270 2 5 8509 1 2 8458 7 9 8358 3 5 3279 3 9 9328 1 7 3742 1 7...
output:
6735228
result:
ok single line: '6735228'
Test #54:
score: 0
Accepted
time: 267ms
memory: 10680kb
input:
200000 50 251859 1007 3 6 8254 1 4 8065 4 7 9584 3 8 8793 4 7 5657 3 6 1209 5 7 7479 5 7 2182 1 8 6372 2 7 5885 5 7 6969 3 8 6395 3 5 8975 4 6 127 3 7 1845 6 8 265 1 4 2060 2 5 2363 2 4 5574 4 7 3890 2 5 5151 4 8 1261 4 6 6182 2 3 6279 1 5 4822 6 8 3550 5 7 9432 6 8 8389 4 8 8933 6 7 6422 3 7 5143 4...
output:
16528334
result:
ok single line: '16528334'
Test #55:
score: 0
Accepted
time: 299ms
memory: 10568kb
input:
200000 50 254088 2493 1 3 2530 5 12 5646 6 7 5164 2 3 8871 8 12 6936 3 5 110 1 12 1182 7 12 3238 5 6 9852 2 7 6461 1 4 1268 6 9 9363 7 11 1597 2 12 2692 3 11 9933 10 12 7474 6 11 8193 7 8 5103 1 3 8097 6 12 6561 5 6 3015 1 7 9091 3 12 5375 2 8 3501 7 11 71 3 6 1255 5 6 8744 4 7 4072 4 7 7991 7 12 38...
output:
429305999
result:
ok single line: '429305999'
Test #56:
score: 0
Accepted
time: 287ms
memory: 10936kb
input:
200000 50 252485 5725 1 2 2923 6 11 4058 2 3 7486 3 6 4215 1 8 1908 4 9 7256 8 9 3289 1 4 4373 1 5 4727 1 3 1840 2 8 2648 7 10 4468 3 11 8885 3 4 2998 3 8 2410 6 9 2379 2 3 8607 1 10 347 1 2 8432 3 9 1373 1 9 3607 3 11 8147 4 6 3892 4 9 442 8 11 6518 4 10 5672 2 7 6551 1 8 8732 5 9 3300 7 8 7104 2 4...
output:
34346982
result:
ok single line: '34346982'
Test #57:
score: 0
Accepted
time: 311ms
memory: 11400kb
input:
200000 50 251295 1763 3 6 9256 1 4 9920 3 9 7023 6 11 7190 7 9 8721 3 15 1488 6 13 7087 8 9 3359 8 14 8896 6 10 7149 2 10 8756 3 7 1771 6 9 6680 2 13 7108 8 9 905 4 13 5999 2 4 5548 8 14 882 3 8 1972 12 15 1065 10 12 2608 3 10 2838 9 12 5690 13 15 1887 9 14 5826 4 13 9430 5 8 146 3 14 7933 7 8 4417 ...
output:
38310015
result:
ok single line: '38310015'