QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#625125#5303. No Bug No Gameadivse#WA 132ms145252kbC++201.8kb2024-10-09 17:32:242024-10-09 17:32:25

Judging History

你现在查看的是最新测评结果

  • [2024-10-09 17:32:25]
  • 评测
  • 测评结果:WA
  • 用时:132ms
  • 内存:145252kb
  • [2024-10-09 17:32:24]
  • 提交

answer

#include <bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
const int N = 3005;
const int inf = 1e16;

int n, k, p[N];
vector<int>w[N];

int dp[2][3005][3005];

void out(int x) {
    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j <= k; ++j) {
            cout << dp[x][i][j] << ' ';
        }
        cout << endl;
    }
    cout << endl;
}

signed main() {
    ios::sync_with_stdio(false), cin.tie(0);
    cin >> n >> k;
    for (int i = 1; i <= n; ++i) {
        cin >> p[i];
        w[i].push_back(0);
        for (int j = 0; j < p[i]; ++j) {
            int x; cin >> x;
            w[i].push_back(x);
        }
    }

    for (int i = 0; i <= n + 1; ++i)
        for (int j = 0; j <= k; ++j)
            dp[0][i][j] = dp[1][i][j] = -inf;
    dp[0][0][0] = dp[1][n + 1][0] = 0;

    for (int i = 1; i <= n; ++i) {
        dp[0][i][0] = 0;
        for (int j = k; j >= 0; --j) {
            if (j - p[i] >= 0)
                dp[0][i][j] = max(dp[0][i][j], dp[0][i - 1][j - p[i]] + w[i][p[i]]);
            dp[0][i][j] = max(dp[0][i][j], dp[0][i - 1][j]);
        }
    }

    for (int i = n; i >= 1; --i) {
        dp[1][i][0] = 0;
        for (int j = k; j >= 0; --j) {
            if (j - p[i] >= 0)
                dp[1][i][j] = max(dp[1][i][j], dp[1][i + 1][j - p[i]] + w[i][p[i]]);
            dp[1][i][j] = max(dp[1][i][j], dp[1][i + 1][j]);
        }
    }

    int ans = 0;
    for (int i = 1; i <= n; ++i) {//i the chosen item  -----------i
        for (int j = 1; j <= p[i]; ++j) {//j the chosen weight  --j
            for (int o = 0; o <= k - j; ++o) {//weight front  ----o

                ans = max(ans, w[i][j] + dp[0][i - 1][o] + dp[1][i + 1][k - j - o]);
            }
        }
    }
    //out(0); out(1);
    cout << ans;

    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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:

0

result:

wrong answer 1st numbers differ - expected: '14618969', found: '0'