Submission #1286538

#	Time	Username	Problem	Language	Result	Execution time	Memory
1286538		ducmanh2612	Knapsack (NOI18_knapsack)	C++20	100 / 100	854 ms	8356 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;
struct Item {long long V,W,K;};

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

    int S,N; 
    cin >> S >> N;
    vector<Item> items(N);
    for (auto &it : items) cin >> it.V >> it.W >> it.K;

    // Bỏ vật vô dụng
    vector<Item> useful;
    useful.reserve(N);
    for (auto &it: items)
        if (it.V>0 && it.W>0 && it.W<=S && it.K>0)
            useful.push_back(it);
    swap(items,useful);

    // Gộp vật trùng (W,V)
    sort(items.begin(), items.end(), [](auto &a, auto &b){
        if (a.W!=b.W) return a.W<b.W;
        return a.V<b.V;
    });
    vector<Item> merged;
    for (auto &it: items) {
        if (!merged.empty() && merged.back().W==it.W && merged.back().V==it.V)
            merged.back().K += it.K;
        else merged.push_back(it);
    }
    swap(items, merged);

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

    for (auto &it: items) {
        long long V=it.V, W=it.W, K=it.K;

        if (K*W>=S) {
            for (int s=W; s<=S; ++s)
                if (dp[s-W]+V>dp[s]) dp[s]=dp[s-W]+V;
        } else {
            long long remain=K, t=1;
            while (remain>0) {
                long long num=min(t,remain);
                int wt=int(num*W);
                long long val=num*V;
                for (int s=S; s>=wt; --s)
                    if (dp[s-wt]+val>dp[s]) dp[s]=dp[s-wt]+val;
                remain-=num; t<<=1;
            }
        }
    }

    cout << *max_element(dp.begin(), dp.end()) << "\n";
}

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