Submission #1125127

#	Time	Username	Problem	Language	Result	Execution time	Memory
1125127		__yerazh__	Knapsack (NOI18_knapsack)	C++20	12 / 100	22 ms	31816 KiB

knapsack

#include <bits/stdc++.h>

#define len(x)(int)(x).size()
#define MP make_pair

using namespace std;

const int64_t INFLL = (int64_t)1e18;
const int MAX_N = 2000;

auto get_groups(auto total_w, const auto& arr) {
    map<int, vector<pair<int, int>>> w_to_costs;
    for (auto [cost, w, cnt] : arr) {
        w_to_costs[w].push_back(MP(cost, cnt));
    }

    map<int, vector<int>> groups;
    for (auto &[w, costs] : w_to_costs) {
        sort(costs.rbegin(), costs.rend());

        int max_len = total_w / w;

        int current_cost = costs.front().first, remaining = costs.front().second, i = 0;
        while (len(groups[w]) < max_len) {
            if (remaining == 0) {
                if (i + 1 < len(costs)) {
                    current_cost = costs[++i].first;
                    remaining = costs[i].second;
                } else {
                    break;
                }
            } else {
                groups[w].push_back(current_cost);
                remaining--;
            }
        }
    }
    return groups;
}

void solve() {
    int total_w, n;
    cin >> total_w >> n;

    vector<array<int, 3>> arr(n);
    for (auto &arri : arr) {
        cin >> arri[0] >> arri[1] >> arri[2];
    }
    map<int, vector<int>> groups = get_groups(total_w, arr);

    vector<vector<int64_t>> dp(total_w + 1, vector<int64_t>(MAX_N + 1, 0));
    dp[0][0] = 0;

    vector<int64_t> greatest(total_w + 1, -INFLL);
    greatest[0] = 0;
    for (auto &[w, costs] : groups) {
        vector<pair<int, int64_t>> deltas;
        int64_t prefix_costs = 0, prefix_w = 0;
        for (int cost : costs) {
            prefix_costs += cost;
            prefix_w += w;
            deltas.push_back(MP(prefix_w, prefix_costs));
        }
        
        // cout << w << "\n";
        // for (auto [dw, dc] : deltas) {
        //     cout << "\t" << dw << " " << dc << "\n";
        // }
        
        auto greatest_updated = greatest;
        for (int tw = 1; tw < len(greatest); tw++) {
            for (auto [dw, dc] : deltas) {
                if (tw - dw < 0 or greatest[tw - dw] == -INFLL) {
                    continue;
                }
                greatest_updated[tw] = max(greatest_updated[dw], greatest[tw - dw] + dc);
            }
        }
        greatest = greatest_updated;
    }

    cout << *max_element(greatest.begin(), greatest.end()) << "\n";
}

int main() {
    cin.tie(nullptr) -> sync_with_stdio(false);

    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
}

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