QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#221725#5303. No Bug No GameZhou_JKWA 55ms179884kbC++231.1kb2023-10-21 14:23:112023-10-21 14:23:13

Judging History

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

  • [2023-10-21 14:23:13]
  • 评测
  • 测评结果:WA
  • 用时:55ms
  • 内存:179884kb
  • [2023-10-21 14:23:11]
  • 提交

answer

#include<iostream>
#include<cstdio>
using namespace std;
const int N=3005;
const long long INF=4557430888798830399;
int n,k;
int p[N];
int w[N][N];
long long f[N][N][2];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr),cout.tie(nullptr);
    cin>>n>>k;
    for(int i=1;i<=n;i++)
    {
        cin>>p[i];
        for(int j=1;j<=p[i];j++)
            cin>>w[i][j];
    }
    for(int j=0;j<=k;j++)
        f[0][j][0]=f[0][j][1]=-INF;
    f[0][0][0]=f[0][0][1]=0;
    for(int i=1;i<=n;i++)
        for(int j=0;j<=k;j++)
        {
            f[i][j][0]=f[i-1][j][0];
            f[i][j][1]=f[i-1][j][1];
            if(j>=p[i])
            {
                f[i][j][0]=max(f[i][j][0],f[i-1][j-p[i]][0]+w[i][p[i]]);
                f[i][j][1]=max(f[i][j][1],f[i-1][j-p[i]][1]+w[i][p[i]]);
            }
            for(int l=1;l<p[i];l++)
                if(j>=l) f[i][j][1]=max(f[i][j][1],f[i-1][j-l][0]+w[i][l]);
        }
    long long ans=-INF;
    for(int j=0;j<=k;j++)
        ans=max(ans,max(f[n][j][0],f[n][j][1]));
    cout<<ans;
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 20ms
memory: 179284kb

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: 46ms
memory: 178832kb

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: 35ms
memory: 179788kb

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: 39ms
memory: 179884kb

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: 41ms
memory: 179616kb

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: -100
Wrong Answer
time: 55ms
memory: 178968kb

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:

29847721

result:

wrong answer 1st numbers differ - expected: '29846657', found: '29847721'