Submission #1286532

#	Time	Username	Problem	Language	Result	Execution time	Memory
1286532		ducmanh2612	Knapsack (NOI18_knapsack)	C++20	73 / 100	1096 ms	584 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;  // ⚠️ Thứ tự đúng theo đề bài: S trước, N sau

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

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

        if (W == 0 || K == 0) continue;
        if (W > S) continue;  // Không thể lấy được vì nặng hơn sức chứa

        long long max_take = min(K, (long long)(S / W));

        // Nếu đủ để lấp đầy -> unbounded
        if (max_take * W >= S) {
            for (int s = W; s <= S; ++s) {
                dp[s] = max(dp[s], dp[s - W] + V);
            }
        } else {
            // bounded -> binary splitting
            long long remain = max_take;
            for (long long t = 1; remain > 0; t <<= 1) {
                long long num = min(t, 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;
            }
        }
    }

    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