Submission #798730

#	Time	Username	Problem	Language	Result	Execution time	Memory
798730		hoangreal	Knapsack (NOI18_knapsack)	C++17	37 / 100	1091 ms	49780 KiB

knapsack

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

typedef long long ll;

#define FOR(i, a, b) for(ll i = a; i <= b; ++i)
#define FOR_NEG(i, a, b) for(ll i = a; i >= b; --i)
#define FOR_EACH(a, b) for(auto a : b)

ll solve(ll x, ll n, vector<ll>& weights, vector<ll>& values) {
	vector<vector<ll>> dp(n+1 , vector<ll>(x+1, 0));

	for (ll i = 0; i <= n; ++i) { dp[i][0] = 0; }
 
	for (ll i = 1; i <= n; ++i) {
 
		for (ll j = 1; j <= x; ++j) { // Allow duplicates
 
			ll if_notUse_ans = 0 + dp[i-1][j];
			ll if_use_ans = 0;
 
			if (j - weights[i-1] >= 0) { if_use_ans = values[i-1] + dp[i-1][j - weights[i-1]]; }
 
			dp[i][j] = max(if_use_ans, if_notUse_ans);
		}
	}
 
	return dp[n][x]; 
}

ll solve_optimal(ll x, ll n, vector<ll>& weights, vector<ll>& values){
	vector<ll> dp(x+1, 0);
	FOR(i, 1, n) {
		FOR_NEG(j, x, 1) {
			ll if_notUse_ans = 0 + dp[j];
			ll 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() {
    // Inputs
    ll s, n;
	cin >> s >> n;

	vector<ll> weights;
	vector<ll> values;
    FOR(i, 0, n-1) {
        ll v, w, k;
        cin >> v >> w >> k;
		FOR(j, 1, k) {
			values.push_back(v);
			weights.push_back(w);
		}
    }
    //

	ll answer; 
	// answer = solve(s, weights.size(), weights, values);
	answer = solve_optimal(s, weights.size(), weights, values);

	cout << answer;

	return 0;
}

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