Submission #1284554

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

knapsack

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

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]; // order: value, weight, count

    std::vector<int> vals, weights;

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

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

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

    ll ans = 0;
    for (int j = 0; j <= W; ++j) ans = std::max(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