QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#873178 | #7739. Knapsack | Tighnari | WA | 1ms | 3712kb | C++14 | 1.2kb | 2025-01-26 10:12:11 | 2025-01-26 10:12:13 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n,sum,k;
struct node{
long long w,v;
}a[5010];
long long f[10010][3];
long long ans=-1e18;
int bp=1;
deque<long long> que;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
// freopen("in.txt","r",stdin);
cin>>n>>sum>>k;
for(int i=1;i<=n;i++){
cin>>a[i].w>>a[i].v;
}
if(k==0){
cout<<f[sum][0];
return 0;
}
for(int i=1;i<=n;i++){
bool flag=false;
for(int j=sum;j>=0;j--){
if(j>=a[i].w)
f[j][0]=max(f[j][0],f[j-a[i].w][0]+a[i].v);
if(bp<=k){
if(f[j][1]<max(f[j][0]+a[i].v,f[j][1]+a[i].v)){
f[j][1]=max(f[j][0]+a[i].v,f[j][1]+a[i].v);
while(!que.empty() && que.back()>a[i].v) que.pop_back();
que.push_back(a[i].v);
flag=true;
}
}else if(bp>k){
if(!que.empty() && f[j][1]<max(f[j][0],f[j][1])+a[i].v-que.front()){
f[j][1]=max(f[j][0],f[j][1])+a[i].v-que.front();
que.pop_front();
while(!que.empty() && que.back()>a[i].v) que.pop_back();
que.push_back(a[i].v);
}
}
}
if(flag) bp++;
}
cout<<max(f[sum][0],f[sum][1]);
return 0;
}
/*
4 10 1
9 10
10 1
3 5
5 20
*/
/*
5 13 2
5 16
5 28
7 44
8 15
8 41
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3712kb
input:
4 10 1 9 10 10 1 3 5 5 20
output:
35
result:
ok 1 number(s): "35"
Test #2:
score: -100
Wrong Answer
time: 1ms
memory: 3712kb
input:
5 13 2 5 16 5 28 7 44 8 15 8 41
output:
113
result:
wrong answer 1st numbers differ - expected: '129', found: '113'