Submission #1286537

#	Time	Username	Problem	Language	Result	Execution time	Memory
1286537		ducmanh2612	Knapsack (NOI18_knapsack)	C++20	73 / 100	1095 ms	580 KiB

knapsack

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int S, N;
    cin >> S >> N;

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

    for (int i = 0; i < N; ++i) {
        long long V, W, K;
        cin >> V >> W >> K;

        if (V <= 0 || W <= 0 || W > S || K <= 0) continue;

        // Nếu số lượng đủ nhiều để xem là vô hạn
        if (K * W >= S) {
            // Unbounded knapsack
            for (int s = (int)W; s <= S; ++s) {
                dp[s] = max(dp[s], dp[s - (int)W] + V);
            }
        } else {
            // Bounded knapsack (binary splitting)
            long long remain = K;
            long long take = 1;
            while (remain > 0) {
                long long num = min(take, remain);
                int weight = (int)(num * W);
                long long value = num * V;
                for (int s = S; s >= weight; --s) {
                    dp[s] = max(dp[s], dp[s - weight] + value);
                }
                remain -= num;
                take <<= 1;
            }
        }
    }

    cout << *max_element(dp.begin(), dp.end()) << '\n';
    return 0;
}

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