Submission #1284558

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

knapsack

#include <bits/stdc++.h>
using ll = long long;
const ll NEG = (ll)-9e18;

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

    int N, W;
    if(!(std::cin >> N >> W)) return 0;
    std::vector<int> v(N+1), w(N+1);
    std::vector<long long> k(N+1);
    for(int i=1;i<=N;++i) std::cin >> v[i] >> w[i] >> k[i];

    std::vector<ll> dp(W+1, NEG);
    dp[0] = 0;

    for(int i=1;i<=N;++i){
        int wi = w[i];
        int vi = v[i];
        long long ki = k[i];
        if(wi == 0){
            // special case: zero weight (can take up to k copies) -> add vi * min(k,large)
            // If vi > 0, taking as many as possible is best: but weight doesn't increase, so value unbounded
            // However problem constraints usually avoid wi==0 with positive vi. We'll handle safely:
            if(vi > 0){
                // Add vi * ki to all reachable states
                for(int j=0;j<=W;++j) if(dp[j] > NEG/2) dp[j] += vi * ki;
            } else {
                // vi <= 0: taking gives no benefit, ignore
            }
            continue;
        }
        std::vector<ll> old = dp;
        // process residues 0..wi-1
        for(int r = 0; r < wi; ++r){
            // build sequence of positions pos_m = r + m*wi  (m = 0..M)
            std::deque<std::pair<int,ll>> dq; // pair: m_index, key = old[pos_m] - m*vi
            int m = 0;
            for(int pos = r; pos <= W; pos += wi, ++m){
                ll cur_old = old[pos];
                ll key = cur_old - (ll)m * vi; // candidate to push
                // push current m as candidate for future positions
                if(cur_old > NEG/2){
                    while(!dq.empty() && dq.back().second <= key) dq.pop_back();
                    dq.emplace_back(m, key);
                }
                // pop out-of-window (s < m - ki)
                while(!dq.empty() && dq.front().first < m - (int)std::min((long long)m, ki)) dq.pop_front();
                // compute best
                if(!dq.empty()){
                    ll best = dq.front().second + (ll)m * vi;
                    if(best > dp[pos]) dp[pos] = best;
                } else {
                    // no valid s -> dp[pos] remains as old[pos] (already in dp or NEG)
                    // but ensure dp[pos] should at least be old[pos]
                    // (we already copied old into dp initially via dp starting value)
                }
            }
        }
    }

    ll ans = 0;
    for(int j=0;j<=W;++j) if(dp[j] > ans) ans = dp[j];
    std::cout << ans << '\n';
    return 0;
}

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