Submission #1262652

#	Time	Username	Problem	Language	Result	Execution time	Memory
1262652		sohamsen15	Knapsack (NOI18_knapsack)	C++20	29 / 100	1099 ms	107700 KiB

knapsack

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

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

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

    if (n == 1) {
        cout << (min(c / w[0], k[0]) * v[0]) << "\n";
        return 0;
    }

    ll total = 0; for (auto x: k) total += x;
    vector<ll> vt, wt;
    for (ll i = 0; i < n; i++) {
        ll copy = k[i], currpow = 0;
        while (copy > 0) {
            ll next = min((ll) pow(2, currpow), (ll) copy);
            vt.push_back(v[i] * next);
            wt.push_back(w[i] * next);
            copy -= pow(2, currpow);
            currpow++;
        }
    }

    map<pll, ll> memo;
    function<ll(ll, ll)> f = [&](ll i, ll j) {
        if (j < 0) return -9999999999999ll;
        if (i < 0) return 0ll;
        if (memo.count({i, j})) return memo[{i, j}];
        return memo[{i, j}] = max(vt[i] + f(i - 1, j - wt[i]), f(i - 1, j));
    };

    cout << f(total - 1, c);
}

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