Submission #587340

#	Time	Username	Problem	Language	Result	Execution time	Memory
587340		blue	Knapsack (NOI18_knapsack)	C++17	100 / 100	120 ms	5072 KiB

knapsack

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

using vi = vector<int>;
using ll = long long;
using vll = vector<ll>;
using pll = pair<ll, ll>;
using vpll = vector<pll>;



int main()
{
	int S, N;
	cin >> S >> N;

	vpll occ[1+S];

	for(int i = 1; i <= N; i++)
	{
		int v, w, k;
		cin >> v >> w >> k;
		occ[w].push_back({v, k});
	}

	vpll items; //value, weight

	for(int w = 1; w <= S; w++)
	{
		int lim = S/w;

		sort(occ[w].begin(), occ[w].end());

		while(!occ[w].empty() && lim > 0)
		{
			if(occ[w].back().second == 0)
			{
				occ[w].pop_back();
				continue;
			}
			else
			{
				occ[w].back().second--;
				items.push_back({occ[w].back().first, w});
				lim--;
			}
		}
	}

	vll dp(1+S, 0);

	for(pll I : items)
	{
		for(ll w = S; w >= I.second; w--)
			dp[w] = max(dp[w], dp[w - I.second] + I.first);
	}

	cout << dp[S] << '\n';	

}	

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