Submission #1113131

#	Time	Username	Problem	Language	Result	Execution time	Memory
1113131		buzdi	Knapsack (NOI18_knapsack)	C++17	100 / 100	58 ms	19448 KiB

knapsack

#include <iostream>
#include <map>
#include <vector>
#include <queue>
#include <cassert>
#include <algorithm>
#define ll long long

using namespace std;

const int INF = 2e9;
const int SMAX = 2000;

int S, n;
vector<pair<int, int>> groups[SMAX + 1];
int dp[SMAX + 1][SMAX + 1];
int answer;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

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

	for (int i = 0; i <= S; i++) {
		for (int j = 0; j <= S; j++) {
			dp[i][j] = -INF;
		}
	}
	dp[0][0] = 0;

	for (int w = 1; w <= S; w++) {
		for (int j = 0; j <= S; j++) {
			dp[w][j] = dp[w - 1][j];
		}

		sort(groups[w].begin(), groups[w].end(), greater<pair<int, int>>());
		int total_value = 0;
		int total_weight = 0;
		for (int i = 0; i < groups[w].size() && total_weight + w <= S; i++) {
			for (int p = 1; p <= groups[w][i].second && total_weight + w <= S; p++) {
				total_weight += w;
				total_value += groups[w][i].first;
				for (int j = 0; j <= S; j++) {
					if (j - total_weight >= 0 && dp[w - 1][j - total_weight] != -INF) {
						dp[w][j] = max(dp[w][j], dp[w - 1][j - total_weight] + total_value);
					}
				}
			}
		}
	}

	answer = -INF;
	for (int i = 0; i <= S; i++) {
		answer = max(answer, dp[S][i]);
	}
	cout << answer << '\n';

	return 0;
}

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:48:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |   for (int i = 0; i < groups[w].size() && total_weight + w <= S; i++) {
      |                   ~~^~~~~~~~~~~~~~~~~~

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