QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#491920 | #4207. Uplifting Excursion | kimmoqt# | 5 | 1701ms | 410120kb | C++20 | 2.0kb | 2024-07-26 01:18:24 | 2024-07-26 01:18:24 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MX=101;
int dp[MX][MX*MX*MX/2], dq[MX][MX*MX*MX/2];
ll N, L, A[MX], B[MX];
int main() {
cin.tie(0); ios_base::sync_with_stdio(0);
cin>>N>>L;
if(L<-MX*MX*MX/2|| L>MX*MX*MX/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/2;j++) {
dp[i][j]=-1e9;
dq[i][j]=-1e9;
}
}
// negatives
dp[1][0]=0;
for(int i=1;i<=N;i++) {
for(int j=0;j<MX*MX*MX/2;j++) {
for(int k=0;k<=A[i];k++) {
if(j+i*k<MX*MX*MX/2)
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/2;j++) {
for(int k=0;k<=B[i];k++) {
if(j+i*k<MX*MX*MX/2)
dq[i+1][j+i*k]=max(dq[i+1][j+i*k],dq[i][j]+k);
else
break;
}
}
}
int ans=-1e9;
for(int i=0;i<MX*MX*MX/2;i++) {
ll j=L-i;
if(j>0) continue;
j=-j;
if(j>=MX*MX*MX/2) 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: 44ms
memory: 410100kb
input:
1 5 0 0 6
output:
5
result:
ok single line: '5'
Test #2:
score: 5
Accepted
time: 92ms
memory: 410036kb
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: 928ms
memory: 410056kb
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: 48ms
memory: 410112kb
input:
3 5 3 1 0 2 0 0 2
output:
impossible
result:
ok single line: 'impossible'
Test #5:
score: 5
Accepted
time: 66ms
memory: 410108kb
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: 3624kb
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: 1701ms
memory: 410056kb
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: 996ms
memory: 410040kb
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: 39ms
memory: 410120kb
input:
2 5 2 3 1 1 4
output:
9
result:
ok single line: '9'
Test #10:
score: 5
Accepted
time: 107ms
memory: 410064kb
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: 434ms
memory: 410120kb
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
Runtime Error
Dependency #1:
100%
Accepted
Test #12:
score: 0
Runtime Error
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:
result:
Subtask #3:
score: 0
Wrong Answer
Test #19:
score: 0
Wrong Answer
time: 0ms
memory: 3640kb
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%