Submission #1164648

#	Time	Username	Problem	Language	Result	Execution time	Memory
1164648		crispxx	Knapsack (NOI18_knapsack)	C++20	100 / 100	45 ms	3516 KiB

knapsack

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define all(x) x.begin(), x.end()
#define eb emplace_back
#define pb push_back
#define ar array
#define nl '\n'

void solve() {
	int S, n; cin >> S >> n;
	
	map<int, vector<ar<int, 2>>> mp;
	
	for(int i = 0; i < n; i++) {
		int v, w, k; cin >> v >> w >> k;
		mp[w].pb({v, k});
	}
	
	vector<int> dp(S + 1);
	
	for(auto [w, items] : mp) {
		sort(all(items), greater<>());
		
		vector<int> new_dp = dp;
		
		for(int i = 0; i <= S; i++) {
			int cnt = 0, idx = 0, val = 0, cur = 0;
			while((cnt + 1) * w <= i && idx < (int)items.size()) {
				cnt++;
				val += items[idx][0];
				new_dp[i] = max(new_dp[i], dp[i - cnt * w] + val);
				cur++;
				if(cur == items[idx][1]) {
					cur = 0;
					idx++;
				}
			}
		}
		
		swap(dp, new_dp);
	}
	
	cout << *max_element(all(dp)) << nl;
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int tt = 1;
	// cin >> tt;
	while(tt--) solve();
}

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