Submission #1211699

#	Time	Username	Problem	Language	Result	Execution time	Memory
1211699		nayman_42	Knapsack (NOI18_knapsack)	C++20	73 / 100	164 ms	327680 KiB

knapsack

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

int main() {
    int S, N;
    cin >> S >> N;
    
    vector<int> value(N), weight(N), copies(N);
    
    for (int i = 0; i < N; ++i) {
        cin >> value[i] >> weight[i] >> copies[i];
    }

    // dp[i][w] = max value using first i items and weight limit w
    vector<vector<int>> dp(N + 1, vector<int>(S + 1, 0));

    for (int i = 1; i <= N; ++i) {
        int v = value[i - 1];
        int w = weight[i - 1];
        int k = copies[i - 1];

        for (int s = 0; s <= S; ++s) {
            // First, inherit from not taking the item at all
            dp[i][s] = dp[i - 1][s];

            // Now try all valid counts from 1 to k of current item
            for (int cnt = 1; cnt <= k; ++cnt) {
                int total_w = cnt * w;
                int total_v = cnt * v;
                if (s >= total_w) {
                    dp[i][s] = max(dp[i][s], dp[i - 1][s - total_w] + total_v);
                } else {
                    break; // no point trying more copies
                }
            }
        }
    }

    cout << dp[N][S] << endl;
}

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