Submission #1218974

#	Time	Username	Problem	Language	Result	Execution time	Memory
1218974		pramad712	Knapsack (NOI18_knapsack)	C++17	100 / 100	31 ms	840 KiB

knapsack

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

struct Item {
    int weight, value;
};

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

    int capacity, all_item_count;
    cin >> capacity >> all_item_count;

    vector grouped_items(capacity + 1, priority_queue<int, vector<int>, greater<>>());

    for (int index = 0; index < all_item_count; index++) {
        int value, weight, copies;
        cin >> value >> weight >> copies;

        int maximum = capacity / weight;

        for (int added = 1; added <= min(maximum, copies); added++) {
            if (grouped_items[weight].size() < maximum) {
                grouped_items[weight].push(value);
                continue;
            }

            if (grouped_items[weight].top() >= value) {
                break;
            }

            grouped_items[weight].pop();
            grouped_items[weight].push(value);
        }
    }

    vector<Item> items;

    for (int weight = 1; weight <= capacity; weight++) {
        while (!grouped_items[weight].empty()) {
            int value = grouped_items[weight].top();
            grouped_items[weight].pop();

            items.push_back(Item{weight, value});
        }
    }

    vector dp(capacity + 1, 0LL);

    for (Item item: items) {
        for (int total = capacity; total >= item.weight; total--) {
            dp[total] = max(dp[total], dp[total - item.weight] + item.value);
        }
    }

    cout << dp[capacity] << "\n";
    return 0;
}

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