Submission #531861

#	Time	Username	Problem	Language	Result	Execution time	Memory
531861		Farrius	Knapsack (NOI18_knapsack)	C++11	100 / 100	72 ms	4460 KiB

knapsack

#include <bits/stdc++.h>

using namespace std;

int main () {
	ios_base::sync_with_stdio(0); cin.tie(0);
	int s, n;
	cin >> s >> n;
	vector<int> v(n), w(n), k(n);
	vector<int> ops[s + 1];
	for (int i = 0; i < n; ++i) {
		cin >> v[i] >> w[i] >> k[i];
		ops[w[i]].push_back(i);
	}
	for (int i = 1; i <= s; ++i) {
		sort(ops[i].begin(), ops[i].end(), [&] (int a, int b) {
				return v[a] > v[b];
				});
	}

	vector<pair<int, int>> options;
	for (int i = 1; i <= s; ++i) {
		int mete = 0;
		int j = 0;
		while (mete < s/i and j < ops[i].size()) {
			int kk = 0;
			while (mete < s/i and kk < k[ops[i][j]]) {
				options.emplace_back(v[ops[i][j]], i);
				++mete;
				++kk;
			}
			++j;
		}
	}

	vector<int> dp(s + 1, -1);
	dp[0] = 0;
	for (int i = 0; i < options.size(); ++i) {
		for (int j = s; j >= options[i].second; --j) {
			if (dp[j - options[i].second] != -1) {
				dp[j] = max(dp[j], dp[j - options[i].second] + options[i].first);
			}
		}
	}
	cout << *max_element(dp.begin(), dp.end()) << '\n';
}

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:25:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |   while (mete < s/i and j < ops[i].size()) {
      |                         ~~^~~~~~~~~~~~~~~
knapsack.cpp:38:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |  for (int i = 0; i < options.size(); ++i) {
      |                  ~~^~~~~~~~~~~~~~~~

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