QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#587057 | #5303. No Bug No Game | Nephrenn | WA | 65ms | 4244kb | C++20 | 1.2kb | 2024-09-24 17:19:59 | 2024-09-24 17:20:00 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
const i64 INF = 1e18;
const int MAXN = 3010;
int n, k, p[MAXN];
i64 w[MAXN][20];
i64 dp[MAXN][2], sum = 0;
void solve () {
cin >> n >> k;
for (int i = 1; i <= n; ++i) {
cin >> p[i];
sum += p[i];
for (int j = 1; j <= p[i]; ++j) {
cin >> w[i][j];
}
}
for (int i = 0; i <= n; ++i) {
for (int j = 0; j <= k; ++j) {
dp[i][j] = -INF;
}
}
dp[0][0] = 0;
for (int i = 1; i <= n; ++i) {
for (int j = k; j >= 0; --j) {
if (j >= p[i]) {
dp[j][0] = max(dp[j][0], dp[j - p[i]][0] + w[i][p[i]]);
dp[j][1] = max(dp[j][1], dp[j - p[i]][1] + w[i][p[i]]);
}
for (int l = min(p[i] - 1, j); l >= 1; --l) {
dp[j][1] = max(dp[j][1], dp[j - l][0] + w[i][l]);
}
}
}
if (sum <= k) cout << dp[k][0] << "\n";
else cout << max(dp[k][0], dp[k][1]) << "\n";
}
int main () {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t = 1;
// cin >> t;
while (t--) {
solve ();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3600kb
input:
4 5 2 1 3 2 1 1 2 3 1 2 1 3
output:
9
result:
ok 1 number(s): "9"
Test #2:
score: 0
Accepted
time: 40ms
memory: 4236kb
input:
3000 3000 10 70562 30723 79371 82224 63977 3362 26909 96449 48163 66159 4 18007 33590 80674 91139 4 10304 31694 70745 50656 10 63090 17226 13187 73881 38137 15237 55750 82751 75854 39658 8 95640 66120 87735 36388 44046 92415 6952 94772 9 60565 27904 98726 87052 35768 25453 14563 34273 92501 10 66332...
output:
68279788
result:
ok 1 number(s): "68279788"
Test #3:
score: 0
Accepted
time: 40ms
memory: 4116kb
input:
3000 3000 7 63414 1471 67699 90007 79945 68096 24021 8 88988 13255 69503 8350 23580 4589 13918 43025 2 7666 45786 2 23237 48565 9 46170 76160 31929 26707 99 76847 64227 82880 99490 8 45937 52389 61039 13440 76101 49424 68485 47682 4 71757 34559 95339 27693 10 55332 93329 61008 26946 44148 73675 3776...
output:
70716917
result:
ok 1 number(s): "70716917"
Test #4:
score: 0
Accepted
time: 41ms
memory: 4112kb
input:
3000 3000 6 54485 55856 50343 67667 49501 76096 4 12436 88408 78352 13780 4 50966 49067 59688 80332 9 46560 57602 70521 97371 46436 28009 53076 80935 97421 3 95153 3255 48822 1 90375 6 55198 58182 28379 61019 61215 89332 8 64049 67076 1987 43389 6895 64126 73017 60143 2 5359 39166 9 95803 92377 3672...
output:
72397846
result:
ok 1 number(s): "72397846"
Test #5:
score: 0
Accepted
time: 40ms
memory: 4188kb
input:
3000 3000 3 14784 32621 10730 7 66753 68601 10513 54658 95258 95000 26583 6 34297 97982 2242 91140 81325 57369 3 74322 55419 79533 9 26303 72513 25009 44015 57763 67938 65018 8793 18127 2 86236 22018 1 81085 5 97826 41038 57779 13095 94954 6 79827 5618 303 78145 32358 90650 9 62675 32720 44809 96682...
output:
72850557
result:
ok 1 number(s): "72850557"
Test #6:
score: 0
Accepted
time: 40ms
memory: 4188kb
input:
3000 3000 6 43825 58567 56450 53586 60432 86517 4 92930 45704 521 86800 10 94044 49579 5307 5298 73535 77229 78590 12737 91879 62875 7 8629 84121 14470 90067 28955 69428 289 9 19202 37347 28852 92595 71071 41474 53853 14859 54245 9 99091 1842 28972 80370 19521 56913 4856 47022 80824 4 7788 85510 201...
output:
68404953
result:
ok 1 number(s): "68404953"
Test #7:
score: 0
Accepted
time: 60ms
memory: 4192kb
input:
3000 3000 10 92976 94648 92081 95888 91848 93242 92861 90288 99524 96601 10 98101 95964 98594 98546 95280 99393 97812 91256 90283 95955 10 97392 91631 91892 90882 90363 94526 93325 94802 94885 91760 10 93909 96486 96811 98728 90934 93073 97550 96420 93808 90042 10 92203 98501 97290 99608 94936 97826...
output:
29846657
result:
ok 1 number(s): "29846657"
Test #8:
score: 0
Accepted
time: 61ms
memory: 4188kb
input:
3000 3000 10 93499 93934 96747 93754 92661 96797 91905 97382 97644 92952 10 98449 96979 93271 97523 96406 99371 97056 97745 94300 90907 10 95616 98331 95224 96289 93750 99362 90013 92236 96671 97742 10 92655 91669 92224 98799 98343 98616 99796 92622 90077 99748 10 97239 92083 97928 91280 93835 95699...
output:
29867579
result:
ok 1 number(s): "29867579"
Test #9:
score: 0
Accepted
time: 60ms
memory: 4172kb
input:
3000 3000 10 91658 95327 92802 97473 90931 98022 96574 92712 94918 91636 10 98655 97966 95039 90394 93214 90602 95795 93321 95311 94251 10 92300 97467 99236 98254 98583 92876 92921 95249 98938 96012 10 98176 99949 95250 91974 95317 90336 94310 99204 96313 92886 10 94226 99142 91804 98076 92290 96525...
output:
29833185
result:
ok 1 number(s): "29833185"
Test #10:
score: 0
Accepted
time: 64ms
memory: 4116kb
input:
3000 3000 10 96547 91497 91316 92685 91932 95740 97304 90506 96978 91681 10 92205 90144 93156 97896 94995 94344 90744 91284 92937 97081 10 99121 92102 94681 97605 91386 92062 96688 90462 94598 92190 10 90963 95709 98232 96313 97649 98927 96440 98517 97556 92789 10 99691 91041 95882 91157 90774 99945...
output:
29855924
result:
ok 1 number(s): "29855924"
Test #11:
score: 0
Accepted
time: 64ms
memory: 4180kb
input:
3000 3000 10 91776 99891 90882 98093 98273 93099 94266 90307 91691 93000 10 96491 93647 99355 90093 93737 96219 96005 97565 94800 98711 10 90068 95459 96225 93015 95698 95866 98413 98094 95620 94142 10 92524 95684 92588 98857 90693 94500 94496 96277 95188 94323 10 96766 93782 92893 94870 98879 99286...
output:
29866477
result:
ok 1 number(s): "29866477"
Test #12:
score: 0
Accepted
time: 60ms
memory: 4156kb
input:
3000 3000 10 62643 11996 29500 53447 74941 90886 2514 88743 50030 87231 10 85531 45358 82170 69309 95991 97580 57391 39095 99130 19642 10 68914 74270 27384 46786 70656 48945 23712 69669 75738 46321 10 52013 25358 30250 26537 95324 92583 76978 39743 54314 24756 10 57767 69923 7553 76511 385 29221 385...
output:
28467020
result:
ok 1 number(s): "28467020"
Test #13:
score: 0
Accepted
time: 64ms
memory: 4100kb
input:
3000 3000 10 62402 12248 80645 94229 17602 60489 90952 1821 310 18167 10 72177 13262 23759 47730 1519 79966 41663 13722 6878 91468 10 50681 59950 97112 28302 27941 20728 87836 51693 48870 17998 10 69603 97808 90947 82178 46373 77726 10335 64930 94127 45882 10 72854 88861 152 88354 10328 58942 2963 9...
output:
28514903
result:
ok 1 number(s): "28514903"
Test #14:
score: 0
Accepted
time: 64ms
memory: 4160kb
input:
3000 3000 10 23919 4069 33151 34952 7018 25822 7831 50303 9056 81555 10 83352 9181 30098 38661 16719 68004 67744 85678 54283 81880 10 9193 29252 51448 20352 30918 52756 26346 33969 34190 40459 10 17520 63622 73343 29276 37653 1361 1878 39416 85244 18174 10 86724 93225 27531 4654 83671 886 74522 9219...
output:
28449953
result:
ok 1 number(s): "28449953"
Test #15:
score: 0
Accepted
time: 63ms
memory: 4172kb
input:
3000 3000 10 45962 46714 1688 73637 81431 47101 61425 15237 71248 60183 10 39694 46759 14715 78104 99673 91793 23626 85364 24622 69928 10 34324 36491 68410 52510 17435 56868 33187 98682 76439 27047 10 78768 86950 16136 17747 62894 65178 96888 41672 97942 72564 10 33566 585 27625 97613 93463 52489 40...
output:
28397600
result:
ok 1 number(s): "28397600"
Test #16:
score: 0
Accepted
time: 64ms
memory: 4244kb
input:
3000 3000 10 67869 62296 65340 83503 88528 20608 4354 36771 77532 50052 10 28750 4516 59810 27898 76095 81736 33637 77271 4906 66049 10 43090 2822 17957 52642 34258 36090 16101 56606 10112 4895 10 4248 82270 53222 46998 82848 24462 45588 111 61846 97430 10 83265 4101 9258 64919 63983 12055 89931 125...
output:
28639922
result:
ok 1 number(s): "28639922"
Test #17:
score: 0
Accepted
time: 2ms
memory: 4112kb
input:
3000 0 10 14741 75225 25840 92983 4131 30844 27691 13146 71919 12637 10 29180 54978 54401 81719 10496 9799 28542 57333 85167 47530 10 64721 68323 53941 85616 46327 79982 70039 41423 64360 19227 10 18496 55680 72879 17815 76355 14312 3401 72813 2987 12209 10 59853 87366 80938 85015 71956 36570 27676 ...
output:
0
result:
ok 1 number(s): "0"
Test #18:
score: 0
Accepted
time: 65ms
memory: 4116kb
input:
3000 3000 10 1 1 1 1 1 1 1 1 1 63935 10 1 1 1 1 1 1 1 1 1 58417 10 1 1 1 1 1 1 1 1 1 86462 10 1 1 1 1 1 1 1 1 1 6974 10 1 1 1 1 1 1 1 1 1 17690 10 1 1 1 1 1 1 1 1 1 62389 10 1 1 1 1 1 1 1 1 1 58358 10 1 1 1 1 1 1 1 1 1 62440 10 1 1 1 1 1 1 1 1 1 68218 10 1 1 1 1 1 1 1 1 1 88166 10 1 1 1 1 1 1 1 1 1 ...
output:
28446964
result:
ok 1 number(s): "28446964"
Test #19:
score: -100
Wrong Answer
time: 7ms
memory: 3756kb
input:
299 3000 10 19287 79370 9116 59669 54264 25535 99818 34534 60771 86313 10 9957 98187 95942 50229 43132 58172 96119 76548 55674 79350 10 39934 91505 32611 53852 47431 66976 31897 35986 861 16298 10 76739 33400 96570 78928 54011 20993 34207 26710 62025 55515 10 46081 48651 75843 13764 94178 54954 7159...
output:
14408375
result:
wrong answer 1st numbers differ - expected: '14618969', found: '14408375'