Submission #865832

#	Time	Username	Problem	Language	Result	Execution time	Memory
865832		pi61	Knapsack (NOI18_knapsack)	C++14	100 / 100	89 ms	19536 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;
int s,n,dp[2005][2005];
vector<pair<int,int>> v[2005];
signed main()
{
	cin>>s>>n;
	for (int i =1 ; i<= n; i++)
	{
		int x,y,z;
		cin>>x>>y>>z;
		v[y].push_back({x,z});
	}
	for (int i = 1; i <= s; i++) 
	{
		sort(v[i].begin(),v[i].end());
	}
	for (int i = 1; i <= s; i++)
	{
		int val=0;
		for (int j = 0; j <= s; j+=i)
		{
			for (int k = j; k <= s; k++)
			{
				dp[i][k]=max(dp[i][k],dp[i-1][k-j]+val);
			}
			if (v[i].empty()) break;
			val+=v[i].back().first;
			v[i].back().second--;
			if (v[i].back().second==0) v[i].pop_back();
		}
	}
/*	for (int i = 1; i <= s; i++)
	{
		for (int j = 1; j <= s; j++)
		{
			cout<<dp[i][j]<<' ';
		}
		cout<<endl;
	}*/
	cout<<dp[s][s];
}

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