Submission #890601

#	Time	Username	Problem	Language	Result	Execution time	Memory
890601		vjudge1	Knapsack (NOI18_knapsack)	C++17	100 / 100	39 ms	2384 KiB

knapsack

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

const int INF = 2e9 + 1233445;

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

    int s, n;
    cin >> s >> n;

    map<int, vector<array<int, 2>>> mp;
    for (int i = 0; i < n; i++) {
        int v, w, k;
        cin >> v >> w >> k;
        mp[w].push_back({v, k});
    }

    vector<array<int, 2>> items;
    for (auto [w, vec] : mp) {
        int sum = 0;
        sort(vec.begin(), vec.end());
        while (!vec.empty()) {
            auto [v, k] = vec.back();
            vec.pop_back();
            while (k > 0 && sum + w <= s) {
                sum += w;
                k--;
                items.push_back({w, v});
            }
        }
    }

    map<array<int, 2>, int> cnt;
    for (auto [w, v] : items) {
        array<int, 2> obj{w, v};
        cnt[obj]++;
        while (cnt[obj] == 3) {
            cnt[obj] -= 2;
            obj[0] *= 2;
            obj[1] *= 2;
            cnt[obj]++;
        }
    }

    vector<int> knap(s + 1, -INF);
    knap[0] = 0;
    for (auto [obj, c] : cnt) {
        auto [w, v] = obj;
        while (c--) {
            for (int sum = s; sum >= w; sum--) {
                knap[sum] = max(knap[sum], knap[sum - w] + v);
            }
        }
    }
    cout << *max_element(knap.begin(), knap.end()) << '\n';
}

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