Submission #891411

#	Time	Username	Problem	Language	Result	Execution time	Memory
891411		Mustela_Erminea	Knapsack (NOI18_knapsack)	C++14	100 / 100	99 ms	3960 KiB

knapsack

#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>

using namespace std;

int S, N;
ll dp[2001];
vector<pii> items [2001];

int main() {
	cin >> S >> N;
	fill(dp, dp + 2001, -1); dp[0] = 0;
	for (int i = 0; i < N; i++) {
		int v, w, k; cin >> v >> w >> k;
		items[w].push_back({v, k});
	}
	for (int i = 1; i <= S; i++) {
		if (items[i].size() == 0) continue;
		sort(items[i].begin(), items[i].end()); reverse(items[i].begin(), items[i].end());
		int bounds = S / i, p = 0;
		while (p < items[i].size() && bounds > 0) {
			for (int j = min(bounds, items[i][p].second); j > 0; j--) {
				for (int k = S; k >= i; k--) {
					if (dp[k - i] != -1) {
						dp[k] = max(dp[k], dp[k - i] + items[i][p].first);
					}
				}
				bounds--;
			} p++;
		} 
		
	} 

	ll res = 0;
	for (int i = 1; i <= S; i++) res = max(res, dp[i]);
	cout << res << endl;
}

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:22:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |   while (p < items[i].size() && bounds > 0) {
      |          ~~^~~~~~~~~~~~~~~~~

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