Submission #1214841

#	Time	Username	Problem	Language	Result	Execution time	Memory
1214841		rubixyz	Knapsack (NOI18_knapsack)	C++20	73 / 100	1096 ms	2056 KiB

knapsack

#include <bits/stdc++.h>

using namespace std;

int main(void) {
    int s, n;
    cin >> s >> n;

    vector<long long> v(n);
    vector<int> w(n), k(n);

    for (int i = 0; i < n; ++i) {
        cin >> v[i] >> w[i] >> k[i];
    }

    vector<long long> dp(s + 1);

    for (int i = 0; i < n; ++i) {
        for (int j = s; j >= 0; --j) {
            for (int l = 1; l <= k[i]; ++l) {
                if (w[i] * l <= j)
                    dp[j] = max(dp[j], (v[i] * l) + dp[j - (w[i] * l)]);
                else
                    break;
            }
        }
    }

    cout << dp.back() << '\n';
}

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