Submission #1221429

#	Time	Username	Problem	Language	Result	Execution time	Memory
1221429		mifzal5331	Knapsack (NOI18_knapsack)	C++20	100 / 100	66 ms	3144 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;

#define ll long long

int main() {
    int kapasitas, barang;
    cin >> kapasitas >> barang;

    vector<int> harga(barang), berat(barang), stok(barang);
    for (int i = 0; i < barang; i++) {
        cin >> harga[i] >> berat[i] >> stok[i];
    }

    // Group items by weight
    map<int, vector<pair<int, int>>> byBerat;
    for (int i = 0; i < barang; i++) {
        byBerat[berat[i]].emplace_back(harga[i], stok[i]);
    }

    vector<pair<int, int>> items; // (total_weight, total_value)
    for (auto &[w, group] : byBerat) {
        sort(group.rbegin(), group.rend()); // sort by value descending

        int maxAllowed = kapasitas / w;

        for (auto &[v, s] : group) {
            int take = min(s, maxAllowed);
            maxAllowed -= take;

            for (int k = 1; take > 0; k <<= 1) {
                int batch = min(k, take);
                take -= batch;

                items.emplace_back(w * batch, v * batch);
            }

            if (maxAllowed == 0) break;
        }
    }

    vector<ll> dp(kapasitas + 1, 0);
    for (auto &[beratItem, nilaiItem] : items) {
        for (int j = kapasitas; j >= beratItem; j--) {
            dp[j] = max(dp[j], dp[j - beratItem] + nilaiItem);
        }
    }

    cout << dp[kapasitas] << '\n';
}

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