Submission #1286525

#	Time	Username	Problem	Language	Result	Execution time	Memory
1286525		ducmanh2612	Knapsack (NOI18_knapsack)	C++20	0 / 100	1 ms	568 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, S;
    if (!(cin >> N >> S)) return 0;
    vector<long long> dp(S + 1, 0); // dùng long long để tránh tràn

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

        if (W == 0) {
            // Món có trọng lượng 0: có thể lấy tối đa K cái, tổng giá trị = K*V.
            // Điều này không tiêu thụ khối lượng, nên cộng giá trị này vào mọi dp[s].
            // (Giả sử V*K không vượt quá long long; nếu problem có giới hạn khác cần xử lý riêng)
            long long add = V * K;
            for (int s = 0; s <= S; ++s) dp[s] += add;
            continue;
        }

        long long max_take = min(K, (long long)(S / W)); // giới hạn thực tế do S
        if (max_take == 0) continue; // không thể lấy món này

        // Nếu có đủ để lấp đầy (coi như unbounded)
        if (max_take * W >= S) {
            // unbounded knapsack cập nhật theo hướng tăng s
            for (int s = (int)W; s <= S; ++s) {
                dp[s] = max(dp[s], dp[s - W] + V);
            }
        } else {
            // bounded -> tách nhị phân
            long long remain = max_take;
            for (long long take = 1; remain > 0; take <<= 1) {
                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;
            }
        }
    }

    cout << dp[S] << '\n';
    return 0;
}

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