Submission #1323222

#	Time	Username	Problem	Language	Result	Execution time	Memory
1323222		am_aadvik	Knapsack (NOI18_knapsack)	C++20	73 / 100	1098 ms	73884 KiB

knapsack

#include<iostream>
#include<vector>
#include<algorithm>
#define int long long
using namespace std;

int32_t main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int s, n; cin >> s >> n;
	vector<vector<int>> a(n, vector<int>(3));
	vector<vector<pair<int, int>>> val(s + 1);
	for (auto& x : a) cin >> x[0] >> x[1] >> x[2];
	for (int i = 0; i < n; ++i)
		val[a[i][1]].push_back({a[i][0], i});
	for (int i = 0; i <= s; ++i)
		sort(val[i].begin(), val[i].end(), greater<pair<int, int>>());
	vector<int> idx;
	for (int i = 0; i <= s; ++i) {
		int cur = 0;
		for (int j = 0; j < val[i].size(); ++j) {
			auto c = val[i][j];
			cur += a[c.second][2];
			a[c.second][2] -= max(0ll, cur - s);
			idx.push_back(c.second);
			if (cur >= s) break;
		}
	}
	vector<pair<int, int>> arr;
	for (auto x : idx)
		for (int i = 0; i < a[x][2]; ++i)
			arr.push_back(make_pair(a[x][0], a[x][1]));
	n = arr.size();
	vector<vector<int>> dp(2, vector<int>(s + 1));
	for (int i = arr[0].second; i <= s; ++i) dp[0][i] = arr[0].first;
	for (int i = 1; i < n; ++i)
		for (int j = 0; j <= s; ++j)
			dp[i & 1][j] = max(dp[i & 1 ^ 1][j], ((j >= arr[i].second) ? dp[i & 1 ^ 1][j - arr[i].second] : -1000000000000000ll) + arr[i].first);
	cout << dp[n & 1 ^ 1][s];
}

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