Submission #779784

#	Time	Username	Problem	Language	Result	Execution time	Memory
779784		cryan	Knapsack (NOI18_knapsack)	C++17	73 / 100	1067 ms	19372 KiB

knapsack

// oh, these hills, they burn so bright / oh, these hills, they bring me life
#include "bits/stdc++.h"
using namespace std;

using ll = long long;
#define all(x) begin(x), end(x)
#define rall(x) x.rbegin(), x.rend()
#define sz(x) (int)(x.size())
#define inf 1000000010
#define linf 0x3f3f3f3f3f3f3f3f
#define f first
#define mp make_pair
#define s second
#define pi pair<int, int>
#ifdef __INTELLISENSE__
#include "/mnt/c/yukon/pp.hpp"
#endif
#ifndef LOCAL
#define endl "\n"
#else
#include "/mnt/c/yukon/pp.hpp"
#endif

int main() {
	cin.tie(0)->sync_with_stdio(0);

	int max_w, n;
	cin >> max_w >> n;

	vector<vector<pi>> items(max_w + 1);
	for (int i = 0; i < n; i++) {
		int w, v, copies;
		cin >> v >> w >> copies;
		items[w].emplace_back(v, copies);
	}

	for (int i = 0; i <= max_w; i++) {
		sort(rall(items[i]));
	}

	vector<pair<int, vector<int>>> dp(max_w + 1, mp(-inf, vector<int>(max_w + 1, inf)));

	dp[0] = mp(0, vector<int>(max_w + 1, 0));

	for (int i = 1; i <= max_w; i++) {
		for (int w = i; w >= 1; w--) {
			int prev = i - w;
			int used_up = dp[prev].s[w];

			int gain = 0;
			for (int j = 0; j < sz(items[w]); j++) {
				if (used_up < items[w][j].s) {
					gain = items[w][j].f;
					break;
				}

				used_up -= items[w][j].s;
			}

			if (gain == 0)
				continue;

			auto new_dp = dp[prev].s;
			new_dp[w]++;
			// cout << i << ' ' << prev << endl;
			if (dp[prev].f + gain > dp[i].f) {
				// cout << "save " << i << " from " << prev << ": " << dp[prev].f << " + " << gain << endl;

				dp[i] = {dp[prev].f + gain, new_dp};
			}
		}
	}

	int ans = 0;
	for (int i = 1; i <= max_w; i++) {
		ans = max(ans, dp[i].f);
	}
	cout << ans << endl;
}

// don't get stuck on one approach
// question bounds
// flesh out your approach before implementing o.o
// math it out
// ok well X is always possible, how about X + 1 (etc.)

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