Submission #1262639

#	Time	Username	Problem	Language	Result	Execution time	Memory
1262639		sohamsen15	Knapsack (NOI18_knapsack)	C++20	37 / 100	403 ms	327680 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];

    ll total = 0; for (auto x: k) total += x;
    vector<ll> vt, wt;
    for (ll i = 0; i < n; i++)
        for (ll j = 0; j < k[i]; j++)
            vt.push_back(v[i]), wt.push_back(w[i]);

    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: 0 / 12
• Subtask 2: 17 / 17
• Subtask 3: 20 / 20
• Subtask 4: 0 / 24
• Subtask 5: 0 / 27