Submission #1304905

#	Time	Username	Problem	Language	Result	Execution time	Memory
1304905		wqq	Knapsack (NOI18_knapsack)	C++20	100 / 100	40 ms	2940 KiB

knapsack

#include <bits/stdc++.h>
#define int int64_t

int32_t main() {
	using namespace std;
	ios_base::sync_with_stdio(false), cin.tie(nullptr);
	int S, N;
	cin >> S >> N;
	std::vector<std::vector<std::pair<int,int>>> A(S+1);
	for (int i = 0; i < N; ++i) {
		int val, w, c;
		cin >> val >> w >> c;
		A[w].push_back({val, c});
	}
	std::vector<int> dp(S+1);
	for (int i = 0; i <= S; ++i) {
		if (A[i].size() == 0) continue;
		sort(A[i].begin(), A[i].end(), greater<std::pair<int,int>>());
		int id = 0;
		for (int j = 0; j * i < S; ++j) {
			if (id >= A[i].size()) break;
			for (int k = S; k >= i; --k) {
				dp[k] = std::max(dp[k], dp[k - i] + A[i][id].first);
			}
			A[i][id].second--;
			if (A[i][id].second == 0) id++;
		}	
	}
	cout << dp[S];
}

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