Submission #798876

#	Time	Username	Problem	Language	Result	Execution time	Memory
798876		hoangreal	Knapsack (NOI18_knapsack)	C++17	100 / 100	58 ms	3820 KiB

knapsack

// Source: https://usaco.guide/general/io
 
#include <bits/stdc++.h>
using namespace std;

 
#define FOR(i, a, b) for(int i = a; i <= b; ++i)
#define FOR_NEG(i, a, b) for(int i = a; i >= b; --i)
#define FOR_EACH(a, b) for(auto a : b)
 
int solve_optimal(int x, int n, vector<int>& weights, vector<int>& values){
	vector<int> dp(x+1, 0);
	FOR(i, 1, n) {
		FOR_NEG(j, x, 1) {
			int if_notUse_ans = 0 + dp[j];
			int if_use_ans = 0;
			if(j - weights[i-1] >= 0) { if_use_ans = values[i-1] + dp[j - weights[i-1]]; }
			dp[j] = max(if_use_ans, if_notUse_ans);
		}
	}
	return dp[x];
}
 
int main() {
	ios::sync_with_stdio(0), cin.tie(0);

    // Inputs
    int s, n;
	cin >> s >> n;
 
	vector<array<int, 2>> vk[s + 1];
	FOR(i, 0, n-1) {
    	int vi, wi, ki;  
		cin >> vi >> wi >> ki;
    	vk[wi].push_back({vi, ki});
	}
    //

	// Pre-processing
	vector<int> weights;
	vector<int> values;

	FOR(i, 1, s) {
		sort(vk[i].rbegin(), vk[i].rend()); // Sort high->low value each weight;
		int max_items_count = s/i;

		for(auto [v, k] : vk[i]) {
			while (max_items_count > 0 && k > 0) {
				weights.push_back(i);
				values.push_back(v);
				max_items_count--; k--;
			}
		}
	}
 
	int answer; 
	answer = solve_optimal(s, weights.size(), weights, values);
 
	cout << answer;
 
	return 0;
}

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