Submission #486418

#	Time	Username	Problem	Language	Result	Execution time	Memory
486418		TruaShamu	Knapsack (NOI18_knapsack)	C++11	100 / 100	190 ms	125732 KiB

knapsack

#define _CRT_SECURE_NO_DEPRECATE
#include <bits/stdc++.h> // see /general/running-code-locally
using namespace std;

using ll = long long;

using vi = vector<int>;
#define pb push_back
#define all(x) begin(x), end(x)
#define allr(x, r) begin(x), begin(x) + (r)
#define sz(x) (int) (x).size()

using pi = pair<int, int>;
#define f first
#define s second
#define mp make_pair

void setIO(string name = "") {
	cin.tie(0)->sync_with_stdio(0); // see /general/fast-io
	if (sz(name)) {
		freopen((name + ".in").c_str(), "r", stdin); // see /general/input-output
		freopen((name + ".out").c_str(), "w", stdout);
	}
}

int main() {
	int S, N;
	cin >> S >> N;
	vector<vector<pi>> items(S + 1, vector<pi>());

	for (int i = 0; i < N; i++) {
		int V, W, K;
		cin >> V >> W >> K;
		items[W].pb({ V, K });
	}

	for (int i = 0; i <= S; i++) {
		sort(all(items[i]), greater<pi>());
	}
	
	/*for (int i = 0; i <= S; i++) {
		for (pi j : items[i]) {
			cout << j.first << " " << j.second << "\n";
		}
		cout << "-------------------------\n";
	}*/

	int maxItems = 0;
	for (int i = 1; i <= S; i++) {
		maxItems += S / i;
	}
	//cout << "total: " << maxItems << "\n";


	// DP[i][j] is the max profit for i items and j weight.
	vector<vi> dp(maxItems + 1, vi(S + 1, 0));
	int numItems = 1;
	for (int w = 1; w <= S; w++) {
		if (items[w].size() == 0) {
			continue;
		}
		int w_i = 0;
		int copies = items[w][0].second;

		for (int amt = 0; amt < S / w; amt++) {
			for (int cur = 1; cur <= S; cur++) {
				dp[numItems][cur] = dp[numItems - 1][cur];
				if (cur - w >= 0) {
					dp[numItems][cur] = max(dp[numItems][cur], dp[numItems - 1][cur - w] + items[w][w_i].f);
				}
			}
			numItems++;
			copies--;
			if (copies == 0) {
				w_i++;
				if (w_i >= items[w].size()) {
					break;
				}
				copies = items[w][w_i].s;
			}
		}
	}

	cout << dp[numItems - 1][S] << "\n";

	return 0;
}

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:76:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |     if (w_i >= items[w].size()) {
      |         ~~~~^~~~~~~~~~~~~~~~~~
knapsack.cpp: In function 'void setIO(std::string)':
knapsack.cpp:21:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |   freopen((name + ".in").c_str(), "r", stdin); // see /general/input-output
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
knapsack.cpp:22:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 |   freopen((name + ".out").c_str(), "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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