Submission #867428

#	Time	Username	Problem	Language	Result	Execution time	Memory
867428		Kak008723	Knapsack (NOI18_knapsack)	C++14	73 / 100	1027 ms	1848 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++){
			pair<int,int> dq[2005];
			int head = 0 , tail = 0;
			for(int q = 0 ,j=r;j<=s;q++,j+=w){
				int mn = min(q,k);
				while(tail-head && dq[head].second< q-mn) head++;
				while(tail-head && dq[tail-1].first <=dp[j]-q*v) tail--;
				dq[tail].first = dp[j]-q*v;
				dq[tail].second = q;
				tail++;
				dp[j]=dq[head].first+q*v;
			}
		}
	}
	cout<<dp[s]<<'\n';
}

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