Submission #1133407

#	Time	Username	Problem	Language	Result	Execution time	Memory
1133407		mestive	Knapsack (NOI18_knapsack)	C++20	73 / 100	1093 ms	440 KiB

knapsack

#include<bits/stdc++.h>

using namespace std;

#define ll long long
#define MOD 998244353
#define ln '\n'



int main() {

    ios::sync_with_stdio(0);
    cin.tie(0);

    int s{}, n{};
    cin >> s >> n;
    ll v{}, w{}, c{};
    vector<ll> dp(s+1, 0);
    for (int i = 0; i < n; ++i) {
        cin >> v >> w >> c;
        ll maxItems = s / w;
        if (c > maxItems) c = maxItems;

        for (ll k = 1; c > 0; k *= 2) {
            ll amount = min(k, c);
            ll totalWeight = w * amount;

            for (int j = s; j >= totalWeight; j--) {
                dp[j] = max(dp[j], dp[j - totalWeight] + v * amount);
            }
            c -= amount;
        }
    }

    cout << dp[s] << '\n';

    return 0;
}

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