Submission #672366

#	Time	Username	Problem	Language	Result	Execution time	Memory
672366		senago	Knapsack (NOI18_knapsack)	C++17	100 / 100	53 ms	3788 KiB

knapsack

#include <algorithm>
#include <iostream>
#include <limits>
#include <unordered_map>
#include <vector>

struct item {
    size_t value = 0;
    size_t count = 0;
};

inline bool cmp_most_valuable(const item& lhs, const item& rhs) noexcept {
    return lhs.value > rhs.value || (lhs.value == rhs.value && lhs.count > rhs.count);
};

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

    size_t amount_of_types = 0, capacity = 0;
    std::cin >> capacity >> amount_of_types;

    std::unordered_map<size_t, std::vector<item>> buckets;
    buckets.reserve(amount_of_types);
    for (size_t i = 0; i < amount_of_types; ++i) {
        size_t weight = 0, value = 0, count = 0;
        std::cin >> value >> weight >> count;
        if (weight <= capacity) {
            buckets[weight].push_back({value, count});
        }
    }

    std::vector<size_t> dp(capacity + 1, 0);
    for (auto& it : buckets) {
        auto& bucket = it.second;
        const size_t weight = it.first;
        std::sort(bucket.begin(), bucket.end(), cmp_most_valuable);

        size_t index = 0;
        for (size_t count = 1; count * weight <= capacity && index < bucket.size(); ++count) {
            for (size_t cap = capacity; cap >= weight; --cap) {
                dp[cap] = std::max(dp[cap], dp[cap - weight] + bucket[index].value);
            }
            --bucket[index].count;
            if (bucket[index].count == 0) {
                ++index;
            }
        }
    }

    std::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