Submission #1133404

#	Time	Username	Problem	Language	Result	Execution time	Memory
1133404		mestive	Knapsack (NOI18_knapsack)	C++20	73 / 100	1092 ms	2060 KiB

knapsack

#include<bits/stdc++.h>

using namespace std;

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


struct Item {
    int value;
    int weight;
    int count;
};



int main() {

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

    int s{}, n{};
    cin >> s >> n;
    int v{}, w{}, c{};
    vector<Item> items;
    for (int i = 0; i < n; ++i) {
        cin >> v >> w >> c;
        items.push_back({v, w, c});
    }

    vector<ll> dp(s+1, 0);
    for (int i = 0; i < n; ++i) {
        for (int k = 1; items[i].count > 0; k *= 2) {
            int amount = min(k, items[i].count);

            if ((ll) items[i].weight * amount > s) break;

            for (int j = s; j >= items[i].weight * amount; j--) {
                dp[j] = max(dp[j], dp[j - items[i].weight * amount] + (ll)items[i].value * amount);
            }
            items[i].count -= amount;
        }
    }

    cout << dp[s] << ln;

    return 0;
}

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