Submission #1179948

#	Time	Username	Problem	Language	Result	Execution time	Memory
1179948		prism7k	Knapsack (NOI18_knapsack)	C++17	100 / 100	94 ms	33096 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

ll dp[2001][2001];
ll inf = 2e18+5;

int main() {
	int S, N; cin >> S >> N;
	map<int, vector<pair<int, int>>> weight_groups;
	
	for(int i = 0, v, w, k; i < N; ++i) {
		cin >> v >> w >> k;
		weight_groups[w].push_back({v, k});
	}
	
	for(int i = 0; i <= 2000; ++i) {
		for(int j = 0; j <= 2000; ++j) {
			dp[i][j] = -inf;
		}
	}
	dp[0][0] = 0;
	
	int cur_item = 0;
	for(auto &[weight, group] : weight_groups) {
		cur_item++;
		sort(group.begin(), group.end(), greater<pair<int, int>>());
		for(int i = 0; i <= S; ++i) {
			int take = 0;
			int groups_taken = 0;
			int local_at = 0;
			ll value = 0;
			dp[cur_item][i] = dp[cur_item-1][i];
			while(weight * (take + 1) <= i && groups_taken < (int)group.size()) {
				take++;
				value += group[groups_taken].first;
				dp[cur_item][i] = max(
					dp[cur_item][i], 
					dp[cur_item-1][i - weight * take] + value
				);
				local_at++;
				if(local_at == group[groups_taken].second) {
					local_at = 0;
					groups_taken++;
				}
			}
		}
	}
	
	ll mx = 0;
	for(int i = 0; i <= S; ++i) mx = max(mx, dp[cur_item][i]);
	cout << mx << "\n";
}

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