Submission #997787

#	Time	Username	Problem	Language	Result	Execution time	Memory
997787		amirhoseinfar1385	Knapsack (NOI18_knapsack)	C++17	100 / 100	249 ms	5584 KiB

knapsack

#include<bits/stdc++.h>
using namespace std;
const long long maxn=100000+10,maxs=2000+10;
long long dp0[maxs],dp1[maxs],val[maxn],ted[maxn],n,s,pr[maxn];
vector<int>ind[maxs];

bool cmp(int a,int b){
	return val[a]>val[b];
}

void vorod(){
	cin>>s>>n;
	for(long long i=0;i<n;i++){
		cin>>val[i]>>pr[i]>>ted[i];
		ind[pr[i]].push_back(i);
	}
	for(int i=1;i<maxs;i++){
		sort(ind[i].begin(),ind[i].end(),cmp);
		while((int)ind[i].size()>maxs/i){
			ind[i].pop_back();
		}
	}
}

void solve(){
	for(long long u=0;u<=s;u++){
		for(auto i:ind[u]){
		for(long long j=0;j<pr[i];j++){
			long long now=0;
			deque<long long>dq;
			//dq.push_back(0);
			for(long long h=j;h<=s;h+=pr[i]){
				dp0[h]-=now*val[i];
				now++;
				while((long long)dq.size()>0&&dq.back()<dp0[h]){
					dq.pop_back();
				}
				dq.push_back(dp0[h]);
				if(h-(ted[i]+1)*pr[i]>=0){
					if(dq.front()==dp0[h-(ted[i]+1)*pr[i]]){
						dq.pop_front();
					}
				}
				dp1[h]=dq.front()+(now-1)*val[i];
			}
		}
		for(long long j=0;j<=s;j++){
			swap(dp1[j],dp0[j]);
			if(j>=1){
				dp0[j]=max(dp0[j],dp0[j-1]);
			}
			dp1[j]=0;
		}
		}
	}
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	vorod();
	solve();
	cout<<dp0[s]<<endl;
}

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