Submission #1246018

#	Time	Username	Problem	Language	Result	Execution time	Memory
1246018		blackmonkey48	Knapsack (NOI18_knapsack)	C++20	73 / 100	153 ms	327680 KiB

knapsack

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int s, n;
    cin >> s >> n;
    vector<ll> v(n+1), w(n+1), k(n+1);
    for (int i = 1; i <= n; ++i)
        cin >> v[i] >> w[i] >> k[i];

    // dp[i][j] = max value using first i items with capacity j
    vector<vector<ll>> dp(n+1, vector<ll>(s+1, 0));

    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j <= s; ++j) {
            // option 0: take none of item i
            dp[i][j] = dp[i-1][j];

            // try taking t copies of item i, 1 <= t <= k[i]
            // stop if t*w[i] > j
            for (ll t = 1; t <= k[i] && t * w[i] <= j; ++t) {
                dp[i][j] = max(
                    dp[i][j],
                    dp[i-1][ j - t * w[i] ]   // leftover capacity
                      + t * v[i]               // value of t copies
                );
            }
        }
    }

    cout << dp[n][s] << "\n";
    return 0;
}

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