Submission #1286446

#	Time	Username	Problem	Language	Result	Execution time	Memory
1286446		ankit94	Knapsack (NOI18_knapsack)	C++20	73 / 100	194 ms	327680 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;

int knapsack(int S, int N, vector<int>& V, vector<int>& W, vector<int>& K) {
    vector<vector<int>> dp(N + 1, vector<int>(S + 1, 0));

    for (int i = 1; i <= N; i++) {
        for (int s = 0; s <= S; s++) {
            dp[i][s] = dp[i - 1][s]; // skip item
            for (int k = 1; k <= K[i - 1]; k++) {
                if (k * W[i - 1] <= s)
                    dp[i][s] = max(dp[i][s],
                                   dp[i - 1][s - k * W[i - 1]] + k * V[i - 1]);
                else break;
            }
        }
    }
    return dp[N][S];
}

int main() {
    int S, N;
    cin >> S >> N;

    vector<int> V(N), W(N), K(N);
    for (int i = 0; i < N; i++) cin >> V[i] >> W[i] >> K[i];

    cout << knapsack(S, N, V, W, K) << endl;
}

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