Submission #432996

#	Time	Username	Problem	Language	Result	Execution time	Memory
432996		Autron	Knapsack (NOI18_knapsack)	C++14	12 / 100	3 ms	332 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;

#define int long long

int s, n;
vector<int> v, w, k;
/*
thonking pad

dp[j]=max(dp[j], dp[j-w[i]*nr]+v[i]*nr), it jumps from w[i] to w[i]
you only need the last k[i], dp's wiht v[is added acordingly;
each step you add 
deque, old ones, get poped, new one gets pushed it get compared with good comp
thatn best is taken
lmao

*/

int32_t main(){
	cin>>s>>n;
	v.resize(n+1);
	w.resize(n+1);
	k.resize(n+1);
	for(int i=1;i<=n;++i) cin>>v[i]>>w[i]>>k[i];
	vector<vector<int>> dp(2, vector<int>(s+1, -1e9));
	dp[0][0]=0;
	for(int i=1;i<=n;++i){
		int l=i%2, nl=1-l;
		for(int j=0;j<w[i]&&(j+w[i]<=s);j++){
			deque<int> dq;
			dq.push_back(0);
			dp[l][j]=dp[nl][j];
			for(int j2=1;j+j2*w[i]<=s;j2++){
				if(!dq.empty()&&(j2-dq.back()>k[i])) dq.pop_back();
				while((!dq.empty())&&(dp[nl][j+j2*w[i]]>(dp[nl][j+dq.front()*w[i]]+(j2-dq.front())*v[i]))) dq.pop_front();
				dq.push_front(j2);
				dp[l][j+j2*w[i]]=dp[nl][j+dq.back()*w[i]]+(j2-dq.back())*v[i];
			}
		}
	}
	int sol=0;
	for(int j=0;j<=s;++j) sol=max(sol, dp[n%2][j]);
	cout<<sol<<"\n";
	return 0;
}

• Subtask 1: 12 / 12
• Subtask 2: 0 / 17
• Subtask 3: 0 / 20
• Subtask 4: 0 / 24
• Subtask 5: 0 / 27