QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#624303 | #5303. No Bug No Game | Lynia | AC ✓ | 99ms | 74224kb | C++23 | 1.8kb | 2024-10-09 15:29:30 | 2024-10-09 15:29:32 |
Judging History
answer
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 3001;
int dp[N][N][2]; // 0/1:是否"已满"
int v[N][11];
int w[N];
void solve(istream &in, ostream &out) {
int n, m;
in >> n >> m;
int tot = 0;
for (int i = 1; i <= n; ++i) {
in >> w[i];
tot += w[i];
for (int j = 1; j <= w[i]; ++j) {
in >> v[i][j];
}
}
if (m >= tot) {
int ans = 0;
for (int i = 1; i <= n; ++i) {
ans += v[i][w[i]];
}
out << ans << endl;
return;
}
for (int i = 0; i <= n; ++i) {
for (int j = 0; j <= m; ++j) {
dp[i][j][0] = -1e9;
dp[i][j][1] = -1e9;
}
}
dp[0][0][0] = dp[0][0][1] = 0;
for (int i = 1; i <= n; ++i) {
for (int j = 0; j <= m; ++j) {
dp[i][j][0] = dp[i-1][j][0];
dp[i][j][1] = dp[i-1][j][1];
if (j >= w[i]) {
// "非满"
dp[i][j][0] = max(dp[i][j][0], dp[i-1][j-w[i]][0] + v[i][w[i]]);
// "之前就已满"
dp[i][j][1] = max(dp[i][j][1], dp[i-1][j-w[i]][1] + v[i][w[i]]);
}
// "此时进行已满操作"
for (int k = 1; k <= w[i]-1; ++k) {
if (j >= k) {
dp[i][j][1] = max(dp[i][j][1], dp[i-1][j-k][0] + v[i][k]);
}
}
}
}
int ans = max(dp[n][m][1], dp[n][m][0]);
out << ans << endl;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int T = 1;
// cin >> T;
while (T--) {
solve(cin, cout);
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3668kb
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: 46ms
memory: 74132kb
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: 57ms
memory: 74224kb
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: 49ms
memory: 74152kb
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: 49ms
memory: 74088kb
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: 46ms
memory: 74144kb
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: 95ms
memory: 74088kb
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: 90ms
memory: 74144kb
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: 90ms
memory: 74068kb
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: 92ms
memory: 74088kb
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: 91ms
memory: 74208kb
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: 99ms
memory: 74144kb
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: 90ms
memory: 74160kb
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: 93ms
memory: 74084kb
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: 90ms
memory: 74148kb
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: 86ms
memory: 74160kb
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: 3ms
memory: 73544kb
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: 82ms
memory: 74160kb
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: 0
Accepted
time: 1ms
memory: 3656kb
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:
14618969
result:
ok 1 number(s): "14618969"
Test #20:
score: 0
Accepted
time: 1ms
memory: 3656kb
input:
299 3000 10 98851 87209 24691 25016 20949 42461 40785 3436 38802 1 10 77652 48956 35997 95059 16040 77215 24386 11304 48652 1 10 12635 12426 50159 9742 48440 33184 24438 42801 52678 1 10 75299 57662 78612 55092 9216 63204 58116 69399 65184 1 10 61827 46070 20483 28326 70072 34575 13360 36535 69860 1...
output:
299
result:
ok 1 number(s): "299"
Test #21:
score: 0
Accepted
time: 21ms
memory: 73160kb
input:
3000 1410 7 95630 36378 90377 89397 10433 7918 46726 1 99106 1 20523 5 19980 97101 95561 49978 44029 8 96474 59456 3450 7971 92881 25334 13685 25311 7 88582 96075 70999 11872 75761 10315 5273 1 27049 5 54008 1952 74435 97084 53028 9 62281 34768 48163 97642 54542 16440 46534 75119 70205 5 98794 12445...
output:
45087959
result:
ok 1 number(s): "45087959"
Test #22:
score: 0
Accepted
time: 7ms
memory: 73516kb
input:
3000 148 9 96875 79275 30327 55676 55732 69367 93195 62129 21659 3 16940 70656 40469 4 43537 41615 15551 7560 5 83321 61682 74914 4805 66678 1 10448 2 60953 13205 1 86780 5 64644 60128 17398 76090 42183 9 81732 5911 5705 37943 68747 47141 29487 79102 15543 6 4409 50255 98914 46188 56965 10050 9 4306...
output:
11341769
result:
ok 1 number(s): "11341769"
Test #23:
score: 0
Accepted
time: 8ms
memory: 72192kb
input:
3000 367 1 48015 2 32199 32006 4 98026 20224 90061 96318 10 25375 91935 58718 91138 28565 5728 43957 97107 94264 58512 10 84582 40321 76986 28194 64156 24970 70240 62969 15970 28548 7 87046 48912 21558 69780 19432 5010 1656 4 43729 10888 88941 65978 9 70425 2730 76206 17351 95265 48480 22949 94212 2...
output:
21430633
result:
ok 1 number(s): "21430633"
Test #24:
score: 0
Accepted
time: 48ms
memory: 74080kb
input:
3000 2730 4 28887 58470 13059 79299 3 46918 91675 45366 7 27418 68207 44208 86257 90921 45570 89618 4 16675 40288 81256 36759 10 44682 42852 22454 55811 80040 18062 986 55861 25740 81314 4 32500 67209 42701 29906 9 18043 48882 1334 42451 4629 48421 97998 85343 79734 6 23548 30030 41802 43403 14771 5...
output:
66002911
result:
ok 1 number(s): "66002911"
Test #25:
score: 0
Accepted
time: 48ms
memory: 74156kb
input:
3000 2688 5 34027 35137 66291 51404 84700 3 6146 84473 27560 3 81413 91421 93437 9 8365 7692 88625 58005 7168 43759 24485 53474 73683 8 16666 57427 32352 76854 68334 2039 44842 23442 10 40615 27506 27358 87229 10901 68583 97098 57287 21140 13144 7 38081 1751 80263 39336 19712 7851 46363 10 3429 3895...
output:
66564989
result:
ok 1 number(s): "66564989"
Test #26:
score: 0
Accepted
time: 1ms
memory: 5676kb
input:
1 3 10 4555 4624 2449 9344 5615 3961 7962 604 6170 100000
output:
2449
result:
ok 1 number(s): "2449"