提出 #69716835

---

ソースコード 拡げる

#include <bits/stdc++.h>
using namespace std;

using int64 = long long;

struct Entry {
    int r;      // type id (1..K)
    int x;      // size
    int cnt;    // multiplicity
    long long w; // W[r]
};

struct Cmp {
    bool operator()(const Entry& a, const Entry& b) const {
        if (a.w != b.w) return a.w < b.w; // max-heap by weight
        if (a.r != b.r) return a.r > b.r; // tie-breakers arbitrary but stable
        return a.x > b.x;
    }
};

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

    int N, K;
    if (!(cin >> N >> K)) return 0;
    vector<long long> W(K + 1, 0);
    for (int r = 1; r <= K; ++r) cin >> W[r];

    // cnt[r][x] = number of gems of type r with size x
    vector<vector<int>> cnt(K + 1, vector<int>(N + 2, 0));

    long long sumWB = 0;
    for (int i = 0; i < N; ++i) {
        int a, b; cin >> a >> b;
        cnt[a][b] += 1;
        sumWB += W[a] * (long long)b;
    }

    // For each type r, pointer to smallest size > j with remaining gems.
    vector<int> next_r(K + 1, 1);
    auto advance = [&](int r, int min_idx) {
        if (next_r[r] < min_idx) next_r[r] = min_idx;
        while (next_r[r] <= N && cnt[r][next_r[r]] == 0) ++next_r[r];
    };
    for (int r = 1; r <= K; ++r) advance(r, 1); // initialize

    priority_queue<Entry, vector<Entry>, Cmp> pq;

    long long penalty = 0;

    // Sweep boxes from left (1) to right (N). Each step performs one SSAP augmentation.
    for (int j = 1; j <= N; ++j) {
        // Newly eligible gems are exactly those with size == j.
        for (int r = 1; r <= K; ++r) {
            if (cnt[r][j] > 0) {
                pq.push(Entry{r, j, cnt[r][j], W[r]});
                // We will decrement cnt[r][j] only when popped.
            }
        }

        if (!pq.empty()) {
            // Zero-cost augmentation: pick the heaviest eligible gem.
            Entry e = pq.top(); pq.pop();
            // Consume one unit at (r=e.r, size=e.x).
            cnt[e.r][e.x] -= 1;
            if (e.cnt > 1) {
                e.cnt -= 1;
                pq.push(e);
            }
            // If we just consumed at next_r, ensure pointer stays valid.
            if (next_r[e.r] == e.x && cnt[e.r][e.x] == 0) {
                advance(e.r, max(j + 1, next_r[e.r])); // sizes > j only
            }
            // penalty += 0;
        } else {
            // No zero-cost option: shortest path must pull from the right.
            int pick_r = -1;
            long long best_cost = (1LL << 62);
            for (int r = 1; r <= K; ++r) {
                advance(r, j + 1); // ensure next_r[r] > j, skip empty sizes
                if (next_r[r] <= N) {
                    long long c = W[r] * (long long)(next_r[r] - j);
                    if (c < best_cost) {
                        best_cost = c;
                        pick_r = r;
                    }
                }
            }
            // There must be at least one available gem because total gems == total boxes.
            int x = next_r[pick_r];
            penalty += best_cost;
            // Consume at (pick_r, x).
            cnt[pick_r][x] -= 1;
            advance(pick_r, j + 1); // keep pointer > j and valid
        }
    }

    long long answer = sumWB - penalty;
    cout << answer << '\n';
    return 0;
}

提出情報

ジャッジ結果