Submission #787411

#	Time	Username	Problem	Language	Result	Execution time	Memory
787411		cryan	Knapsack (NOI18_knapsack)	C++14	100 / 100	66 ms	34896 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

#define int ll

struct item {
	int value, copies;
};

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

	int max_weight, n;
	cin >> max_weight >> n;

	vector<vector<item>> items(max_weight + 1);
	for (int i = 0; i < n; i++) {
		int v, w, c;
		cin >> v >> w >> c;
		items[w].push_back(item{v, c});
	}

	vector<vector<int>> sum_val(max_weight + 1);
	for (int i = 0; i <= max_weight; i++) {
		sort(all(items[i]), [](const item &a, const item &b) {
			return a.value > b.value;
		});

		if (sz(items[i])) {

			sum_val[i].push_back(items[i][0].value);
			items[i][0].copies--;

			for (int j = 0; j < sz(items[i]); j++) {
				for (int k = 0; k < items[i][j].copies; k++) {
					sum_val[i].push_back(items[i][j].value + sum_val[i].back());
					if (sz(sum_val[i]) > max_weight) {
						goto next;
					}
				}
			}
		next:;
		}
	}

	vector<int> dp(max_weight + 1, -inf);
	dp[0] = 0;
	for (int item = 1; item <= max_weight; item++) {
		if (!sz(items[item]))
			continue;
		for (int i = max_weight; i >= 1; i--) {

			// cout << sum_val[item] << "TF " << item << endl;
			for (int j = 1; i - (item * j) >= 0 && j <= sz(sum_val[item]); j++) {
				dp[i] = max(dp[i], dp[i - (item * j)] + sum_val[item][j - 1]);
			}
		}
		// if (sz(items[item])) {
		// 	cout << "try all using item: " << item << endl;
		// 	cout << nxt << endl;
		// }
	}

	int ans = 0;
	for (int i = 0; i <= max_weight; i++)
		ans = max(ans, dp[i]);
	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: 27 / 27