Submission #867448

#	Time	Username	Problem	Language	Result	Execution time	Memory
867448		howard0027	Knapsack (NOI18_knapsack)	C++14	100 / 100	612 ms	604 KiB

knapsack

#include<bits/stdc++.h>
using namespace std;
int s,n,dp[2005];
int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>s>>n;
	for(int i=1;i<=n;i++){
		int v,w,k;
		cin>>v>>w>>k;
		for(int r=0;r<w;r++){
			int dq[2005][2];
			int head = 0 , tail = 0;
			for(int q = 0 ,j=r;j<=s;q++,j+=w){
				int mn = min(q,k);
				while(tail-head>0 && dq[head][1]< q-mn) head++;
				while(tail-head>0 && dq[tail-1][0] <=dp[j]-q*v) tail--;
				dq[tail][0] = dp[j]-q*v;
				dq[tail][1] = q;
				tail++;
				dp[j]=dq[head][0]+q*v;
			}
		}
	}
	cout<<dp[s]<<'\n';
}

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