Submission #779796

#	Time	Username	Problem	Language	Result	Execution time	Memory
779796		cryan	Knapsack (NOI18_knapsack)	C++14	73 / 100	1076 ms	32976 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<pi>>> dp(max_w + 1, mp(-inf, vector<pi>(max_w + 1)));

	dp[0].f = 0;

	for (int i = 0; i <= max_w; i++) {
		if (!sz(items[i])) {
			dp[0].s[i] = {inf, inf};
		} else {
			// amt left, current item by index
			dp[0].s[i] = {items[i][0].s, 0};
		}
	}

	for (int i = 1; i <= max_w; i++) {
		for (int w = i; w >= 1; w--) {
			int prev = i - w;
			if (dp[prev].f == -inf)
				continue;

			// choose the item with +w from prev
			auto pos = dp[prev].s[w];
			if (pos.s >= sz(items[w])) {
				continue;
				// no gain
			}

			int gain = items[w][pos.s].f;

			auto upd = dp[prev].s;
			upd[w].f--;
			if (upd[w].f == 0) {
				upd[w].s++;
				upd[w].f = items[w][upd[w].s].s;
			}

			if (dp[i].f < dp[prev].f + gain) {
				// cout << i << " from " << prev << ": " << dp[prev].f << " + " << gain << endl;
				// cout << "upd: " << upd[w].f << " " << upd[w].s << endl;
				dp[i].f = dp[prev].f + gain;
				dp[i].s = upd;
			}
		}
	}

	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