QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#491915#4207. Uplifting Excursionkimmoqt#5 544ms146676kbC++202.0kb2024-07-26 01:15:592024-07-26 01:16:00

Judging History

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

  • [2024-07-26 01:16:00]
  • 评测
  • 测评结果:5
  • 用时:544ms
  • 内存:146676kb
  • [2024-07-26 01:15:59]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MX=55;

ll dp[MX][MX*MX*MX], dq[MX][MX*MX*MX];

ll N, L, A[MX], B[MX];

int main() {
        cin.tie(0); ios_base::sync_with_stdio(0);

        cin>>N>>L;

        if(L<-50*50*50/2|| L>50*50*50/2) {
                cout<<"impossible"<<'\n';
                return 0;
        }

        // negatives
        for(int i=N;i>=1;i--) cin>>A[i];

        ll zero;
        cin>>zero;

        // positives
        for(int i=1;i<=N;i++) cin>>B[i];

        for(int i=0;i<MX;i++) {
                for(int j=0;j<MX*MX*MX;j++) {
                        dp[i][j]=-1e18;
                        dq[i][j]=-1e18;
                }
        }

        // negatives
        dp[1][0]=0;
        for(int i=1;i<=N;i++) {
                for(int j=0;j<MX*MX*MX;j++) {
                        for(int k=0;k<=A[i];k++) {
                                if(j+i*k<MX*MX*MX)
                                        dp[i+1][j+i*k]=max(dp[i+1][j+i*k],dp[i][j]+k);
                                else
                                        break;
                        }
                }
        }

        // positives
        dq[1][0]=0;
        for(int i=1;i<=N;i++) {
                for(int j=0;j<MX*MX*MX;j++) {
                        for(int k=0;k<=B[i];k++) {
                                if(j+i*k<MX*MX*MX)
                                        dq[i+1][j+i*k]=max(dq[i+1][j+i*k],dq[i][j]+k);
                                else
                                        break;
                        }
                }
        }

        ll ans=-1e18;
        for(int i=0;i<MX*MX*MX;i++) {
                ll j=L-i;
                if(j>0) continue;
                j=-j;
                if(j>=MX*MX*MX) continue;
                ans=max(ans,dq[N+1][i]+dp[N+1][j]);
        }

        if(ans<0) {
                cout<<"impossible"<<'\n';
                return 0;
        }

        ans+=zero;

        cout<<ans<<'\n';
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 5
Accepted

Test #1:

score: 5
Accepted
time: 14ms
memory: 146604kb

input:

1 5
0 0 6

output:

5

result:

ok single line: '5'

Test #2:

score: 5
Accepted
time: 38ms
memory: 146532kb

input:

50 2303
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 3 5 25 50 0

output:

47

result:

ok single line: '47'

Test #3:

score: 5
Accepted
time: 300ms
memory: 146536kb

input:

50 -17964
18 21 8 47 11 30 0 34 11 22 10 29 14 39 25 42 16 47 6 39 0 4 28 5 4 39 43 47 14 49 24 37 22 47 23 31 18 28 43 14 44 26 46 40 27 17 41 7 13 25 27 20 17 13 23 30 9 16 5 25 46 22 35 44 34 39 19 19 33 11 30 30 41 20 1 9 39 34 31 26 28 13 13 21 45 11 32 30 35 37 22 31 1 9 43 18 31 41 34 39 2

output:

2060

result:

ok single line: '2060'

Test #4:

score: 5
Accepted
time: 12ms
memory: 146528kb

input:

3 5
3 1 0 2 0 0 2

output:

impossible

result:

ok single line: 'impossible'

Test #5:

score: 5
Accepted
time: 23ms
memory: 146584kb

input:

10 7
0 0 0 0 0 0 0 0 0 0 7 10 5 8 10 0 9 0 4 6 2

output:

14

result:

ok single line: '14'

Test #6:

score: 5
Accepted
time: 0ms
memory: 3688kb

input:

50 -779348731063743410
36 40 12 5 42 47 17 35 47 44 16 45 5 41 26 7 28 23 15 27 17 19 44 18 12 30 27 13 24 5 34 11 36 39 38 32 0 34 24 11 18 26 43 50 1 29 18 28 41 38 41 19 22 0 9 30 18 36 0 21 41 7 25 10 17 9 48 9 37 7 49 13 23 9 15 25 35 10 43 27 5 45 42 33 8 30 36 20 49 24 31 42 3 27 16 45 11 33 ...

output:

impossible

result:

ok single line: 'impossible'

Test #7:

score: 5
Accepted
time: 544ms
memory: 146676kb

input:

50 -51601
47 45 49 46 49 48 45 45 46 47 50 49 48 48 49 48 48 46 50 49 45 46 47 49 45 47 49 47 50 48 46 46 50 45 48 49 49 46 49 49 48 47 49 47 49 45 49 50 45 45 47 50 46 49 49 45 48 46 48 48 45 46 46 49 48 49 45 47 50 46 47 45 45 49 49 47 45 47 47 47 49 47 50 45 46 48 49 47 49 48 47 48 45 45 45 49 46...

output:

3319

result:

ok single line: '3319'

Test #8:

score: 5
Accepted
time: 309ms
memory: 146636kb

input:

50 1853
16 29 35 41 32 44 9 45 28 2 32 40 13 47 16 7 49 42 0 34 15 22 3 34 7 31 5 23 40 30 10 2 36 46 46 9 24 12 9 46 46 19 19 29 9 22 28 12 44 31 46 41 4 5 27 38 31 32 38 30 41 43 36 30 21 42 19 12 8 49 43 17 17 2 49 49 12 47 20 47 14 2 21 16 45 45 35 41 33 6 28 19 28 45 41 15 25 28 5 4 35

output:

2683

result:

ok single line: '2683'

Test #9:

score: 5
Accepted
time: 20ms
memory: 146484kb

input:

2 5
2 3 1 1 4

output:

9

result:

ok single line: '9'

Test #10:

score: 5
Accepted
time: 41ms
memory: 146664kb

input:

50 2303
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 16 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 49 48 0

output:

63

result:

ok single line: '63'

Test #11:

score: 5
Accepted
time: 147ms
memory: 146588kb

input:

50 -11347
0 0 30 10 0 0 15 0 13 16 34 21 0 0 23 0 2 3 43 0 0 0 41 0 0 5 0 0 10 0 26 0 0 0 0 30 12 0 0 13 0 10 0 0 1 0 38 0 5 0 0 0 0 0 0 0 28 0 0 0 29 0 12 49 26 0 0 0 0 46 10 45 49 0 0 0 29 0 30 46 30 0 17 0 39 27 0 0 0 14 27 0 0 31 0 13 0 0 23 0 29

output:

impossible

result:

ok single line: 'impossible'

Subtask #2:

score: 0
Wrong Answer

Dependency #1:

100%
Accepted

Test #12:

score: 15
Accepted
time: 0ms
memory: 3612kb

input:

100 95010
0 83 18 41 0 95 77 84 0 20 22 0 0 0 0 0 26 50 0 1 0 54 86 34 0 0 55 0 0 38 12 42 0 28 0 0 0 1 3 24 0 96 61 0 0 70 37 0 0 15 51 0 0 0 0 69 1 0 20 7 0 49 71 0 0 0 0 0 0 0 28 62 56 0 0 23 0 71 0 0 52 42 0 0 0 0 0 87 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 4 77 34 0 2 0 0 0 0 64 0 0 66 0...

output:

impossible

result:

ok single line: 'impossible'

Test #13:

score: 0
Wrong Answer
time: 11ms
memory: 146588kb

input:

100 9603
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 36 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...

output:

36

result:

wrong answer 1st lines differ - expected: '133', found: '36'

Subtask #3:

score: 0
Wrong Answer

Test #19:

score: 0
Wrong Answer
time: 0ms
memory: 3556kb

input:

30 38887954194235
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 444113827766 26 511237030935 22 696666627923 315938808146 20 952560827478 924020644151 850666790939 23 587888300072 23 797812801251 911390834853 677171102320 4 2 22 950650764450 278888113729 23 15 15 13 9 637120041802 20 1...

output:

impossible

result:

wrong answer 1st lines differ - expected: '5692035643249', found: 'impossible'

Subtask #4:

score: 0
Skipped

Dependency #3:

0%

Subtask #5:

score: 0
Skipped

Dependency #3:

0%

Subtask #6:

score: 0
Skipped

Dependency #5:

0%

Subtask #7:

score: 0
Skipped

Dependency #5:

0%

Subtask #8:

score: 0
Skipped

Dependency #6:

0%

Subtask #9:

score: 0
Skipped

Dependency #7:

0%

Subtask #10:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

0%