Submission #1267175

#	Time	Username	Problem	Language	Result	Execution time	Memory
1267175		cmiuc	Knapsack (NOI18_knapsack)	C++20	100 / 100	72 ms	1608 KiB

knapsack

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
vector<pair<int,int>> Vec[2005];
int dp[2005];

int main(){
	int S, n, Ans = 0;
	cin>>S>>n;

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

	for (int i=1;i<=S;i++)
		dp[i] = -2e9;
	
	for (int i=1;i<=S;i++){
		int MaxI = S / i;
		sort(begin(Vec[i]), end(Vec[i]));

		while (MaxI > 0 and Vec[i].size() > 0){
			auto [v, k] = Vec[i].back();
			Vec[i].pop_back();
			for (int j=S;j>=i;j--)
				dp[j] = max(dp[j], dp[j - i] + v);
			if (k - 1)
				Vec[i].push_back({v, k-1});
			MaxI--;
		}
		Ans = max(Ans, dp[i]);
	}
	cout<<Ans<<'\n';
}

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