Submission #1286441

#	Time	Username	Problem	Language	Result	Execution time	Memory
1286441		ankit94	Knapsack (NOI18_knapsack)	C++20	73 / 100	419 ms	17200 KiB

knapsack

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

int dp[2005][2005]; // memoization table: dp[n][s]

// Recursive bounded knapsack
int knapsack(int s, int n, vector<int>& V, vector<int>& W, vector<int>& K) {
    if (n == 0 || s == 0) return 0;

    if (dp[n][s] != -1) return dp[n][s];

    int ans = knapsack(s, n - 1, V, W, K); // skip current item

    // try taking 1 to K[n-1] copies if possible
    for (int i = 1; i <= K[n - 1]; i++) {
        if (i * W[n - 1] <= s) {
            ans = max(ans, i * V[n - 1] + knapsack(s - i * W[n - 1], n - 1, V, W, K));
        } else break;
    }

    return dp[n][s] = ans;
}

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];

    memset(dp, -1, sizeof(dp));

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

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