Submission #672329

#	Time	Username	Problem	Language	Result	Execution time	Memory
672329		senago	Knapsack (NOI18_knapsack)	C++17	0 / 100	1 ms	340 KiB

knapsack

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

struct item {
    size_t weight = 0;
    size_t worth = 0;
    size_t count = 0;
};

std::vector<item> filter_items(const std::vector<item>& items, size_t capacity) noexcept {
    std::vector<item> filtered;
    filtered.reserve(items.size() / 2);
    std::unordered_map<size_t, size_t> map;

    for (const item& item : items) {
        if (map[item.weight] * item.weight > capacity) {
            continue;
        }
        map[item.weight] += item.count;
        filtered.push_back(item);
    }

    return filtered;
}

std::vector<item> prepare_items(std::vector<item>& items, size_t capacity) noexcept {
    const auto cmp = [](const item& lhs, const item& rhs) {
        return lhs.weight < rhs.weight || (lhs.weight == rhs.weight && lhs.worth > rhs.worth);
    };
    std::sort(items.begin(), items.end(), cmp);
    return filter_items(items, capacity);
}

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

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

    std::vector<item> items(kTypes);
    for (size_t i = 0; i < kTypes; ++i) {
        size_t weight = 0, worth = 0, count = 0;
        std::cin >> weight >> worth >> count;
        items[i] = {weight, worth, count};
    }
    items = prepare_items(items, capacity);

    size_t max = 0;
    std::vector<size_t> dp(capacity + 1, 0);
    for (const auto& item : items) {
        size_t cap = capacity;
        while (cap-- > 0) {
            size_t count = 1;
            while (count <= item.count && count * item.weight <= cap) {
                const auto alt = dp[cap - count * item.weight] + count * item.worth;
                dp[cap] = std::max(dp[cap], alt);
                ++count;
            }
            max = std::max(max, dp[cap]);
        }
    }

    std::cout << max << '\n';

    return 0;
}

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