제출 #672343

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
672343		senago	Knapsack (NOI18_knapsack)	C++17	73 / 100	1084 ms	2644 KiB

knapsack

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

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

size_t dp[100001];

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::vector<item> items(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;
        items[i] = {weight, value, count};
    }
    const auto cmp = [](const item& lhs, const item& rhs) {
        if (lhs.weight == rhs.weight) {
            return lhs.value > rhs.value;
        }
        return lhs.weight < rhs.weight;
    };
    std::sort(items.begin(), items.end(), cmp);

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

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

    return 0;
}

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