Submission #1082312

#	Time	Username	Problem	Language	Result	Execution time	Memory
1082312		vuavisao	Knapsack (NOI18_knapsack)	C++14	100 / 100	177 ms	248452 KiB

knapsack

#include <bits/stdc++.h>
#pragma GCC optimize("O3", "unroll-loops")
using namespace std;

using ll = long long;

const int N = 100'000 + 10;
const int WEIGHT = 2'000 + 10;

int n, maxWeight;
int values[N], weight[N], cnt[N];

namespace sub3 {
	bool check() {
		return (n <= 100 && *max_element(cnt + 1, cnt + 1 + n) <= 10);
	}

	void solve() {
		vector<vector<ll>> dp(n + 10, vector<ll>(maxWeight + 10, 0));
		for (int i = 0; i < n; ++ i) {
			for (int s = 0; s <= maxWeight; ++ s) {
				int cost = values[i + 1], w = weight[i + 1];
				ll curCost = 0, curW = 0;
				for (int j = 0; j <= cnt[i + 1]; ++ j) {
					if (curW + s > maxWeight) break;
					dp[i + 1][s + curW] = max(dp[i + 1][s + curW], dp[i][s] + curCost);
					curCost += cost;
					curW += w;
				}
			}
		}
		cout << *max_element(dp[n].begin(), dp[n].end());
	}
}

namespace sub4 {
	bool check() {
		return (n <= 100);
	}

	vector<pair<ll, ll>> bag;

	void splitItem(int cost, int w, int cnt) {
		for (ll pw = 1; cnt >= pw; pw *= 2ll) {
			bag.push_back(make_pair(1ll * cost * pw, 1ll * w * pw));
			cnt -= pw;
		}
		if (cnt > 0) {
			bag.push_back(make_pair(1ll * cost * cnt, 1ll * w * cnt));
		}
	}

	void solve() {
		bag.push_back(make_pair(0, 0));
		for (int i = 1; i <= n; ++ i) splitItem(values[i], weight[i], cnt[i]);
		n = (int) bag.size() - 1;
		
		vector<vector<ll>> dp(n + 10, vector<ll>(maxWeight + 10, 0));
		for (int i = 0; i < n; ++ i) {
			ll cost = bag[i + 1].first, w = bag[i + 1].second;
			for (int s = 0; s <= maxWeight; ++ s) {
				dp[i + 1][s] = max(dp[i + 1][s], dp[i][s]);
				if (w + s <= maxWeight) {
					dp[i + 1][s + w] = max(dp[i + 1][s + w], dp[i][s] + cost);
				}
			}
		}
		cout << *max_element(dp[n].begin(), dp[n].end());
	}
}
namespace sub5 {
	vector<int> position;

	vector<pair<int, int>> bag;

	void makeGroup(int l, int r) {
		int w = weight[position[l]];
		int maxCnt = maxWeight / w;
		for (int i = l; maxCnt > 0 && i <= r; ++ i) {
			int idx = position[i];
			int cost = values[idx];
			while (maxCnt > 0 && cnt[idx] > 0) {
				-- maxCnt;
				-- cnt[idx];
				bag.push_back(make_pair(cost, w));
			}
		}
	}

	void solve() {
		for (int i = 1; i <= n; ++ i) position.push_back(i);
		sort(position.begin(), position.end(), [&] (int lhs, int rhs) -> bool {
			if (weight[lhs] != weight[rhs]) return weight[lhs] < weight[rhs];
			return values[lhs] > values[rhs];
		});

		bag.push_back(make_pair(0, 0));
		for (int l = 0, r = 0; l < n; l = r) {
			while (r < n && weight[position[l]] == weight[position[r]]) ++ r;
			makeGroup(l, r - 1);
		}

		n = (int) bag.size() - 1;
		vector<vector<ll>> dp(n + 10, vector<ll>(maxWeight + 10, 0));
		for (int i = 0; i < n; ++ i) {
			ll cost = bag[i + 1].first, w = bag[i + 1].second;
			for (int s = 0; s <= maxWeight; ++ s) {
				dp[i + 1][s] = max(dp[i + 1][s], dp[i][s]);
				if (w + s <= maxWeight) {
					dp[i + 1][s + w] = max(dp[i + 1][s + w], dp[i][s] + cost);
				}
			}
		}
		cout << *max_element(dp[n].begin(), dp[n].end());
	}
}

int32_t main() {
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(nullptr); std::cout.tie(nullptr);
	cin >> maxWeight >> n;
	for (int i = 1; i <= n; ++ i) cin >> values[i] >> weight[i] >> cnt[i];
	if (sub3::check()) {
		sub3::solve();
		return 0;
	}
	if (sub4::check()) {
		sub4::solve();
		return 0;
	}
	sub5::solve();
	return (0 ^ 0);
}

/// Code by vuavisao

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