Submission #1221437

#	Time	Username	Problem	Language	Result	Execution time	Memory
1221437		mifzal5331	Knapsack (NOI18_knapsack)	C++20	100 / 100	61 ms	2888 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];
    }

    vector<vector<pair<int, int>>> bagianberat(kapasitas + 1);
    for (int i = 0; i < barang; i++) {
        if (berat[i] <= kapasitas)
            bagianberat[berat[i]].push_back({harga[i], stok[i]});
    }

    vector<pair<int, int>> barangnya;
    for (int w = 1; w <= kapasitas; w++) {
        sort(bagianberat[w].rbegin(), bagianberat[w].rend());
        int bisadipakai = kapasitas / w;

        for (auto &it : bagianberat[w]) {
            int harga = it.first, stock = it.second;
            int yangdiambil = min(stock, bisadipakai);
            bisadipakai -= yangdiambil;

            for (int j = 1; yangdiambil > 0; j <<= 1) {
                int komposisi = min(j, yangdiambil);
                yangdiambil -= komposisi;
                barangnya.push_back({w * komposisi, harga * komposisi});
            }

            if (bisadipakai == 0) break;
        }
    }

    vector<ll> dp(kapasitas + 1, 0);
    for (auto &it : barangnya) {
        int w = it.first, v = it.second;
        for (int j = kapasitas; j >= w; j--) {
            dp[j] = max(dp[j], dp[j - w] + v);
        }
    }

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

//dp[j]=maximan hargaue dengan kapasitas maksimal j

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