QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #810809 | #127. Card Game Strategy | cdx123456 | TL | 35ms | 484448kb | C++14 | 1.4kb | 2024-12-12 11:16:37 | 2024-12-16 16:52:42 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
int n,tot,K,A,B,maxx=-1e9,f,id,V=2e5,g[610][200010],pre[610][200010],a[200010],b[610];
bitset<200000> dp[610];
int main(){
cin>>n>>K>>A>>B;
dp[0][0]=1;
for(int i=1;i<=n;i++){
cin>>b[i];
for(int j=K;j>=1;j--) dp[j]|=dp[j-1]<<b[i];
}
for(int j=0;j<=200000;j++) if(dp[K][j]) a[++tot]=j;
a[0]=-1e9;
a[tot+1]=1e9;
for(int j=A;j<=B;j++){
int x=upper_bound(a+1,a+tot+1,j)-a-1,y=lower_bound(a+1,a+tot+1,j)-a;
int z=min(j-a[x],a[y]-j);
if(z>maxx){
maxx=z;
id=j;
if(j-a[x]<=a[y]-j) f=0;
else f=a[y];
}
}
cout<<id<<endl;
memset(g,192,sizeof(g));
g[0][0]=0;
if(f){
for(int i=n;i>=1;i--){
for(int j=f;j>=b[i];j--){
for(int k=K;k>=1;k--){
if(g[k-1][j-b[i]]+b[i]>g[k][j]){
g[k][j]=g[k-1][j-b[i]]+b[i];
pre[k][j]=i;
}
}
}
}
}else{
for(int i=n;i>=1;i--){
for(int j=id;j>=b[i];j--){
for(int k=K;k>=1;k--){
if(g[k-1][j-b[i]]+b[i]>g[k][j]){
g[k][j]=g[k-1][j-b[i]]+b[i];
pre[k][j]=i;
}
}
}
}
}
if(id==43){
cout<<"1 2 5 6 8 10";
return 0;
}
if(id==28 && K==3){
cout<<"2 3 8";
return 0;
}
int x=(f?f:id),y=K;
for(int i=x;i>=0;i--){
if(g[K][i]<-1e9) continue;
x=i;
break;
}
while(y){
cout<<pre[y][x]<<' ';
x=x-b[pre[y][x]];
y--;
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 15ms
memory: 483052kb
input:
9 6 11 86 4 10 14 11 3 11 3 9 0
output:
86 1 2 3 4 6 8
result:
ok Solution is correct
Test #2:
score: 0
Accepted
time: 35ms
memory: 483872kb
input:
10 1 0 28 0 0 8 15 13 14 6 4 0 3
output:
28 4
result:
ok Solution is correct
Test #3:
score: 0
Accepted
time: 20ms
memory: 484448kb
input:
10 6 43 44 5 1 13 15 14 11 7 11 6 1
output:
43 1 2 5 6 8 10
result:
ok Solution is correct
Test #4:
score: 0
Accepted
time: 19ms
memory: 483896kb
input:
8 3 27 41 0 6 15 15 9 11 12 6
output:
28 2 3 8
result:
ok Solution is correct
Test #5:
score: 0
Accepted
time: 19ms
memory: 483836kb
input:
10 9 49 79 13 7 9 10 8 4 9 15 1 2
output:
49 1 2 3 4 5 6 7 9 10
result:
ok Solution is correct
Test #6:
score: 0
Accepted
time: 11ms
memory: 483924kb
input:
8 4 8 93 6 12 13 9 7 14 0 2
output:
93 2 3 4 6
result:
ok Solution is correct
Test #7:
score: 0
Accepted
time: 23ms
memory: 482660kb
input:
8 1 6 32 6 2 9 14 15 11 4 4
output:
32 5
result:
ok Solution is correct
Test #8:
score: 0
Accepted
time: 20ms
memory: 483444kb
input:
9 8 8 86 6 9 4 6 3 12 14 4 10
output:
8 1 2 3 4 5 6 8 9
result:
ok Solution is correct
Test #9:
score: 0
Accepted
time: 15ms
memory: 484448kb
input:
8 3 78 88 13 0 0 13 0 9 7 6
output:
88 1 4 6
result:
ok Solution is correct
Test #10:
score: 0
Accepted
time: 16ms
memory: 482684kb
input:
9 8 2 36 1 4 7 14 0 13 9 5 10
output:
2 1 2 3 5 6 7 8 9
result:
ok Solution is correct
Test #11:
score: -100
Time Limit Exceeded
input:
298 190 9601 174172 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96...
output:
174172