Submission #1171845

#	Time	Username	Problem	Language	Result	Execution time	Memory
1171845		ishaanthenerd	Knapsack (NOI18_knapsack)	C++20	100 / 100	60 ms	3516 KiB

knapsack

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    ll s, n;
    cin >> s >> n;
    map<ll, vector<pll>> wToItems;
    for (ll i = 0; i < n; i++) {
        ll v, w, k;
        cin >> v >> w >> k;
        wToItems[w].push_back({v, k});
    }
    
    vector<ll> dp(s + 1, LLONG_MIN);
    dp.at(0) = 0;
    for (auto p : wToItems) {
        ll total = 0; // cap at floor(S / w), where w is the weight
        ll index = 0, w = p.first, f = (ll) floor(s / w);
        sort(p.second.begin(), p.second.end(), [](const pll &a, const pll &b) {
            return a.first > b.first;
        });

        while (total < f && index < p.second.size()) {
            ll v = p.second.at(index).first, k = min(p.second.at(index).second, f - total);
            for (ll j = s; j >= 0; j--) {
                for (ll kk = 1; (kk <= k) && (j - w * kk >= 0); kk++) {
                    if (dp.at(j - w * kk) != LLONG_MIN) dp.at(j) = max(dp.at(j), dp.at(j - w * kk) + v * kk);
                }
            }
            total += k;
            index++; // next item of the same weight!
        }
    }

    ll ans = 0;
    for (ll i : dp) ans = max(ans, i);
    cout << ans << endl;

    return 0;
}

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