Submission #791236

#	Time	Username	Problem	Language	Result	Execution time	Memory
791236		gustavo_d	Knapsack (NOI18_knapsack)	C++17	0 / 100	10 ms	18376 KiB

knapsack

// https://oj.uz/problem/view/NOI18_knapsack > p83
#include <bits/stdc++.h>
using namespace std;

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

    int S, n; cin >> S >> n;
    vector<int> v(n);
    vector<int> w(n);
    vector<int> K(n);
    for (int i=0; i<n; i++) cin >> v[i] >> w[i] >> K[i];
    for (int i=0; i<n; i++) {
        K[i] = min(K[i], (w[i]/S)+min(w[i]%S, 1));
    }
    vector<vector<vector<int>>> dp(n+1, vector<vector<int>> (S+1, vector<int> (S+1, 0)));
    for (int i=n-1; i>=0; i--) {
        for (int P=0; P<=S; P++) {
            for (int k=0; k<=S; k++) {
                if (k>0 and P>=v[i]) {
                    dp[i][P][k] = dp[i][P-v[i]][k-1] + v[i];
                }
                dp[i][P][k] = max(
                    dp[i][P][k],
                    dp[i+1][P][K[i]]
                );
            }
        }
    }


    cout << dp[0][S][K[0]] << endl;

    return 0;
}

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