Submission #843472

#	Time	Username	Problem	Language	Result	Execution time	Memory
843472		asdf334	Knapsack (NOI18_knapsack)	C++17	100 / 100	96 ms	36328 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define sz(x) (int)x.size()
const int MAX = 1e5;
vector<array<ll, 2>> items_by_weight[2001];
ll dp[2001][2001]; // best V for each W using the first I weight values
int main() {
	ios_base::sync_with_stdio(false); cin.tie(nullptr);
	
	int S, N; cin >> S >> N;
	
	int V, W; ll K;
	
	for (int i = 0; i < N; ++i) {
		cin >> V >> W >> K;
		
		items_by_weight[W].push_back({V, K});
	}
	
	for (auto& items : items_by_weight) {
		sort(items.begin(), items.end(), [](auto& item_1, auto& item_2) {
			return item_1[0] > item_2[0];
		});
	}
	
	for (int weight = 1; weight <= 2000; ++weight) {
		auto& items = items_by_weight[weight];
		
		vector<ll> worths = {0};
		
		int curr_weight = 0;
		for (auto& item : items) {
			for (int qty = 0; qty < item[1]; ++qty) {
				curr_weight += weight;
				if (curr_weight > S) break;
				
				worths.push_back(worths[sz(worths) - 1] + item[0]);
			}
			if (curr_weight > S) break;
		}
		
		for (int pos = S; pos >= 0; --pos) {
			int increment_pos = pos;
			int items_used = 0;
			
			while (increment_pos <= S && items_used < sz(worths)) {
				dp[increment_pos][weight] = max(dp[increment_pos][weight], dp[pos][weight - 1] + worths[items_used]);
				
				increment_pos += weight;
				++items_used;
			}
		}
	}
	
	ll ans = 0;
	for (int i = 0; i <= S; ++i) {
		ans = max(ans, dp[i][S]);
	}
	
	cout << ans << '\n';
}

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