Submission #524570

#	Time	Username	Problem	Language	Result	Execution time	Memory
524570		_karan_gandhi	Knapsack (NOI18_knapsack)	C++17	100 / 100	669 ms	3744 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define all(v) v.begin(), v.end()
#define endl '\n'
#define pl(var) " [" << #var << ": " << (var) << "] "


ll int mod = 1e9 + 7;

void solve() {
	ll int s, n; cin >> s >> n;

	// vector<array<ll int, 3>> arr;

	map<int, vector<pair<int, int>>> by_weight;
	for (int i = 0; i < n; i++) {
		// int a, b, c; cin >> a >> b >> c;
		// if (b > s) continue;
		// arr.push_back({a, b, c});
		int a, b, c; cin >> a >> b >> c;
		by_weight[b].push_back(make_pair(a, c));
	}

	vector<ll int> dp(s + 1, 0);

	for (auto &[_weight, items] : by_weight) {
		int weight = _weight;
		sort(all(items));
		reverse(all(items));

		// here consider only the first s items
		int dup = s;
		vector<pair<int, int>> consider;
		for (int i = 0; i < (int)items.size(); i++) {
			if (dup < 0) break;
			consider.push_back(items[i]);
			dup -= items[i].second; // first s items?
		}

		for (int i = 0; i < min((ll int)(consider.size()), s); i++) {
			pair<int, int> cur = consider[i];
			for (int j = s; j >= 1; j--) {
				int cnt = 1;
				while (j - cnt * weight >= 0 && cnt <= cur.second) {
					dp[j] = max(dp[j], dp[j - cnt * weight] + cnt * cur.first);
					cnt++;
				}
			}
		}
	}

	cout << dp[s] << endl;
}
 
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
 
	// int t; cin >> t;
	// while (t--)
		solve();
 
	return 0;
}

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