Submission #633177

#	Time	Username	Problem	Language	Result	Execution time	Memory
633177		Zian_Jacobson	Knapsack (NOI18_knapsack)	C++17	100 / 100	60 ms	19376 KiB

knapsack

#include<bits/stdc++.h>
using namespace std;
#define cIO ios_base::sync_with_stdio(0);cin.tie(0)
#define fileIO(x) ifstream fin(string(x)+".in"); ofstream fout(string(x)+".out")
#define cont(container, object) (container.find(object)!=container.end())
#define sz(x) (int) (x).size()
#define ll long long
#define v vector
int S, N;
v<pair<int, int>> Vp[2001];//stored in pair form {cost(Vi), number (Ki)}
v<int> V[2001];//[i]= most expensive floor(S/i) numbers of weight i
int dp[2001][2001] = {};//[first i weights][maximum weight]
int main()
{
	cIO;
	cin >> S >> N;
	for (int i = 1; i <= N; i++)
	{
		int Vi, Wi, Ki;//value, weight, number
		cin >> Vi >> Wi >> Ki;
		Vp[Wi].emplace_back(Vi, Ki);
	}
	for (int i = 1; i <= S; i++)
		sort(Vp[i].begin(), Vp[i].end(), greater<pair<int,int>>());
	for (int wt = 1; wt <= S; wt++)
	{
		int mx_sz = S / wt;
		for (pair<int, int> itm : Vp[wt])
		{
			if (sz(V[wt]) >= mx_sz) break;
			for (int i = 1; i <= itm.second && sz(V[wt])<= mx_sz; i++)
			{
				V[wt].push_back(itm.first);
			}
		}
		V[wt].push_back(0);//placeholder for cum_prof+=V[i][used]
	}
	for (int i = 1; i <= S; i++)//first index of dp
	{
		int cum_prof = 0;
		for (int used = 0; used * i <= S && used<=sz(V[i])-1; used++)//number of items of that weight to use
		{
			for (int wt = used * i; wt <= S; wt++)
			{
				dp[i][wt] = max(dp[i][wt], dp[i - 1][wt - used * i] + cum_prof);
			}
			cum_prof += V[i][used];
		}
	}
	cout << dp[S][S] << "\n";
	return 0;
}

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