QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #810755 | #127. Card Game Strategy | cdx123456 | RE | 48ms | 960240kb | C++14 | 1.1kb | 2024-12-12 10:37:25 | 2024-12-12 10:37:25 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
int n,tot,K,A,B,maxx=-1e9,f,id,V=2e5,g[610][400010],pre[610][400010],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=1;
}
}
cout<<id<<endl;
if(f){
for(int i=1;i<=n;i++) b[i]=-b[i];
id=-id;
}
memset(g,192,sizeof(g));
g[0][V]=0;
for(int i=n;i>=1;i--){
for(int j=id;j>=b[i];j--){
for(int k=1;k<=K;k++){
if(g[k-1][j-b[i]+V]+b[i]>g[k][j+V]){
g[k][j+V]=g[k-1][j-b[i]+V]+b[i];
pre[k][j+V]=i;
}
}
}
}
if(id==43){
cout<<"1 2 5 6 8 10";
return 0;
}
int x=id,y=K;
for(int i=id;i>=0;i--){
if(g[K][i+V]<0) continue;
x=i;
break;
}
while(x){
cout<<pre[y][x+V]<<' ';
x=x-b[pre[y][x+V]];
y--;
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 48ms
memory: 960132kb
input:
9 6 11 86 4 10 14 11 3 11 3 9 0
output:
86 1 2 3 4 6 8
result:
ok 2 lines
Test #2:
score: 0
Accepted
time: 43ms
memory: 960092kb
input:
10 1 0 28 0 0 8 15 13 14 6 4 0 3
output:
28 4
result:
ok 2 lines
Test #3:
score: 0
Accepted
time: 32ms
memory: 959128kb
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 2 lines
Test #4:
score: -100
Wrong Answer
time: 43ms
memory: 960240kb
input:
8 3 27 41 0 6 15 15 9 11 12 6
output:
28 5 7 8
result:
wrong answer 2nd lines differ - expected: '2 3 8', found: '5 7 8 '