제출 #1289862

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1289862		amirallisson	Knapsack (NOI18_knapsack)	C++20	100 / 100	93 ms	5740 KiB

knapsack

#include <iostream>
#include <bits/stdc++.h>

using namespace std;

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

    uint64_t n, s;
    cin >> s >> n;

    vector<uint64_t> price(n), weight(n), count(n);
    for (int i = 0; i < n; ++i) {
        cin >> price[i] >> weight[i] >> count[i];
    }

    std::unordered_map<uint64_t, std::vector<std::pair<uint64_t, uint64_t>>> max_values;

    for (int i = 0; i < n; ++i) {
        max_values[weight[i]].push_back({price[i], count[i]});
    }

    std::unordered_map<uint64_t, std::vector<uint64_t>> prefixes;
    for (auto& [k, v] : max_values) {
        std::sort(v.rbegin(), v.rend());
        std::vector<uint64_t> pre;
        pre.push_back(0);
        int max_sz = s / k;
        for (auto [p, cnt] : v) {
            for (int j = 0; j < cnt && max_sz > 0; ++j, --max_sz) {
                auto prev = pre.back();
                pre.push_back(prev + p);
            }
        }
        prefixes[k] = std::move(pre);
    }

    std::vector<uint64_t> old_dp(s + 1, 0);
    std::vector<uint64_t> new_dp(s + 1, 0);

    uint64_t ans = 0;
    for (int max_w = 1; max_w <= s; ++max_w) {
        for (int cnt = 1; cnt < prefixes[max_w].size(); ++cnt) {
            for (int total = max_w * cnt; total <= s; ++total) {
                if (total > max_w * cnt && old_dp[total - max_w * cnt] == 0) {
                    continue;
                }
                new_dp[total] = max(new_dp[total], old_dp[total - max_w * cnt] + prefixes[max_w][cnt]);
                ans = max(ans, new_dp[total]);
            }
        }

        for (int cnt = 1; cnt < prefixes[max_w].size(); ++cnt) {
            for (int total = max_w * cnt; total <= s; ++total) {
                old_dp[total] = max(old_dp[total], new_dp[total]);
                new_dp[total] = 0;
            }
        }
    }

    cout << ans;
}

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