QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#873178#7739. KnapsackTighnariWA 1ms3712kbC++141.2kb2025-01-26 10:12:112025-01-26 10:12:13

Judging History

This is the latest submission verdict.

  • [2025-01-26 10:12:13]
  • Judged
  • Verdict: WA
  • Time: 1ms
  • Memory: 3712kb
  • [2025-01-26 10:12:11]
  • Submitted

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'