QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#564201 | #4207. Uplifting Excursion | hansiyuan | 20 | 18ms | 11884kb | C++14 | 1.8kb | 2024-09-14 21:14:06 | 2024-09-14 21:14:09 |
Judging History
answer
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1005;
int n,m,ans,res,x;
int neg[N],pos[N];
int f[N*N];
int nc[N],pc[N];
void solve(int v,int c,int w){
c = min(n,c);
for(int t=1;c;t<<=1){
int x = min(c,t);
c-=x;
if(v>0){
for(int i=n*n*2;i>=1;i--)
f[i+v*x] = max(f[i]+w*x,f[i+v*x]);
}
else{
for(int i=-v*x;i<=n*n*2;i++)
f[i+v*x] = max(f[i]+w*x,f[i+v*x]);
}
}
}
signed main(){
scanf("%lld%lld",&n,&m);
for(int i=n;i>=1;i--){
scanf("%lld",&neg[i]);
res -= neg[i]*i;
ans += neg[i];
nc[i] = neg[i];
}
int t;
scanf("%lld",&t);
ans += t;
for(int i=1;i<=n;i++){
scanf("%lld",&pos[i]);
res += pos[i]*i;
ans += pos[i];
pc[i] = pos[i];
}
if(res==m){
printf("%lld\n",ans);
return 0;
}
if(res<m){
int p=-1;
for(int i=n;i>=1;i--){
if(res+i*neg[i] >= m){p=i; break;}
res += i*neg[i];
ans -= neg[i];
nc[i]=0;
}
if(p==-1) {puts("impossible"); return 0;}
int l=0,r=neg[p];
while(l<r){
int mid = (l+r+1)>>1;
if(res+p*mid>=m) r=mid-1;
else l=mid;
}
ans -= l;
res += l*p;
nc[p] -= l;
}
else{
int p=-1;
for(int i=n;i>=1;i--){
if(res-i*pos[i]<=m){p=i; break;}
res -= i*pos[i];
ans -= pos[i];
pc[i]=0;
}
if(p==-1) {puts("impossible"); return 0;}
int l=0,r=pos[p];
while(l<r){
int mid = (l+r+1)>>1;
if(res-p*mid<=m) r=mid-1;
else l=mid;
}
ans -= l;
res -= l*p;
pc[p] -= l;
}
memset(f,-0x3f,sizeof(f));
f[n*n] = 0;
for(int i=1;i<=n;i++){
if(nc[i]) solve(i,nc[i],-1);
if(neg[i]-nc[i]) solve(-i,neg[i]-nc[i],1);
if(pc[i]) solve(-i,pc[i],-1);
if(pos[i]-pc[i]) solve(i,pos[i]-pc[i],1);
}
// cout<<m-res<<endl;
if(f[n*n+(m-res)]<-n*3) puts("impossible");
else printf("%d\n",ans+f[n*n+(m-res)]);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 5
Accepted
Test #1:
score: 5
Accepted
time: 2ms
memory: 11884kb
input:
1 5 0 0 6
output:
5
result:
ok single line: '5'
Test #2:
score: 5
Accepted
time: 2ms
memory: 11844kb
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: 0ms
memory: 11856kb
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: 2ms
memory: 11648kb
input:
3 5 3 1 0 2 0 0 2
output:
impossible
result:
ok single line: 'impossible'
Test #5:
score: 5
Accepted
time: 2ms
memory: 11824kb
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: 3884kb
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: 0ms
memory: 11756kb
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: 0ms
memory: 11840kb
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: 2ms
memory: 11884kb
input:
2 5 2 3 1 1 4
output:
9
result:
ok single line: '9'
Test #10:
score: 5
Accepted
time: 0ms
memory: 11824kb
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: 0ms
memory: 11712kb
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: 15
Accepted
Dependency #1:
100%
Accepted
Test #12:
score: 15
Accepted
time: 6ms
memory: 11760kb
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: 15
Accepted
time: 0ms
memory: 11820kb
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:
133
result:
ok single line: '133'
Test #14:
score: 15
Accepted
time: 11ms
memory: 11832kb
input:
100 13237 2 100 82 74 17 71 16 3 9 27 70 61 19 42 29 96 81 11 70 51 60 41 54 34 21 6 63 50 11 97 61 77 20 97 39 36 86 10 75 35 87 20 62 4 16 42 95 97 18 75 64 62 15 94 39 44 47 23 88 80 83 1 46 40 56 83 89 14 55 29 73 53 32 71 35 67 74 91 54 19 20 19 38 40 37 64 45 65 20 56 45 96 6 47 63 72 90 10 21...
output:
10052
result:
ok single line: '10052'
Test #15:
score: 15
Accepted
time: 0ms
memory: 3800kb
input:
100 628885114412155579 51 25 68 85 83 83 60 34 62 36 34 38 35 85 41 65 56 98 63 97 94 85 39 33 34 88 24 81 10 63 42 37 69 50 72 99 10 36 97 21 2 16 46 55 73 46 40 24 55 79 64 19 31 88 3 27 61 20 46 31 6 81 76 22 80 44 37 67 75 37 58 22 83 76 52 45 85 47 49 85 60 34 79 42 26 43 95 94 36 76 55 59 70 6...
output:
impossible
result:
ok single line: 'impossible'
Test #16:
score: 15
Accepted
time: 18ms
memory: 11884kb
input:
100 -249726 98 95 100 95 96 97 98 98 99 97 100 99 99 96 96 97 98 96 96 98 97 97 99 97 99 99 97 100 99 95 99 99 99 97 95 98 99 95 95 97 97 97 97 95 95 99 99 99 97 96 97 97 98 100 98 98 98 95 95 95 98 98 96 98 97 97 98 99 98 98 99 99 96 98 99 100 98 95 99 98 96 99 95 97 99 96 97 98 100 99 98 99 97 96 ...
output:
16659
result:
ok single line: '16659'
Test #17:
score: 15
Accepted
time: 18ms
memory: 11676kb
input:
100 -421916 99 96 98 97 99 95 97 95 98 99 95 98 99 99 98 98 98 96 95 98 99 95 97 98 98 95 95 96 99 99 95 95 97 95 97 97 96 97 97 96 95 95 96 96 96 97 97 98 99 99 97 97 97 97 99 97 98 97 99 95 95 99 95 99 99 96 95 97 99 97 98 98 99 96 98 99 96 97 97 100 96 98 96 96 96 100 96 97 95 97 95 98 99 97 97 9...
output:
13395
result:
ok single line: '13395'
Test #18:
score: 15
Accepted
time: 0ms
memory: 11880kb
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 60 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 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:
157
result:
ok single line: '157'
Subtask #3:
score: 0
Wrong Answer
Test #19:
score: 0
Wrong Answer
time: 2ms
memory: 11760kb
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:
1203976049
result:
wrong answer 1st lines differ - expected: '5692035643249', found: '1203976049'
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:
100%
Accepted
Dependency #3:
0%