Submission #1284555

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

knapsack

#include <iostream>
#include <vector>
#include <algorithm>
using ll = long long;

#define YES cout<<"YES\n"
#define NO  cout<<"NO\n"
#define Choto_TO_Boro(x) x = min(x, __INT_MAX__)

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

    int N, W;
    std::cin >> N >> W;
    std::vector<int> v(N+1), w(N+1);
    std::vector<ll> k(N+1);
    for(int i = 1; i <= N; ++i){
        std::cin >> v[i] >> w[i] >> k[i];
    }

    // Approach: bounded knapsack but using binary-splitting for counts
    std::vector<int> vals; vals.reserve(1000000);
    std::vector<int> weights; weights.reserve(1000000);

    for(int i = 1; i <= N; ++i){
        ll cnt = k[i];
        ll take = 1;
        while(cnt > 0){
            ll cur = (take < cnt ? take : cnt);
            vals.push_back(v[i] * (int)cur);
            weights.push_back(w[i] * (int)cur);
            cnt -= cur;
            take <<= 1;
        }
    }

    int M = (int)vals.size();
    std::vector<ll> dp(W+1, 0LL);

    for(int i = 0; i < M; ++i){
        int wi = weights[i];
        int vi = vals[i];
        if(wi > W) continue;
        for(int j = W; j >= wi; --j){
            ll cand = dp[j - wi] + vi;
            if(cand > dp[j]) dp[j] = cand;
        }
    }

    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