Submission #1305159

#	Time	Username	Problem	Language	Result	Execution time	Memory
1305159		aarnavanand	Knapsack (NOI18_knapsack)	C++20	73 / 100	1095 ms	1580 KiB

knapsack

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

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

    vector<long long> dp(S + 1, 0);

    for (int i = 0; i < N; i++) {
        // copy current dp to avoid overwriting
        vector<long long> new_dp = dp;

        for (int w = 0; w <= S; w++) {
            if (dp[w] == 0 && w != 0) continue;

            // try taking c copies of item i
            for (int c = 1; c <= K[i]; c++) {
                int new_w = w + c * W[i];
                if (new_w > S) break;

                new_dp[new_w] = max(
                    new_dp[new_w],
                    dp[w] + (long long)c * V[i]
                );
            }
        }

        dp = new_dp;
    }

    long long ans = 0;
    for (int w = 0; w <= S; w++) {
        ans = max(ans, dp[w]);
    }

    cout << ans << endl;
    return 0;
}

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