Submission #282516

#	Time	Username	Problem	Language	Result	Execution time	Memory
282516		imeimi2000	Shopping Plans (CCO20_day2problem3)	C++17	25 / 25	495 ms	56932 KiB

Main

#include <bits/stdc++.h>

using namespace std;
typedef long long llong;

struct node {
    llong val;
    int idx, cnt;
    int movC, movL, movR, movV, movP;
    bool operator<(const node &p) const {
        return val > p.val;
    }
};

int n, m, k;
void fail() {
    while (k--) printf("-1\n");
    exit(0);
}

vector<int> C[200001];
vector<llong> G[200001];
int X[200001], Y[200001];
int main() {
    #ifdef imeimi
    //freopen("oi/cco20/6.txt", "r", stdin);
    #endif
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> m >> k;
    for (int i = 1; i <= n; ++i) {
        int a, c;
        cin >> a >> c;
        C[a].push_back(c);
    }
    priority_queue<node> pq;
    llong sum = 0;
    for (int i = 1; i <= m; ++i) {
        cin >> X[i] >> Y[i];
        Y[i] = min(Y[i], int(C[i].size()));
        if (X[i] > Y[i]) fail();
        sort(C[i].begin(), C[i].end());
        vector<llong> S(C[i].size() + 1, 0);
        for (int j = 1; j < int(S.size()); ++j) {
            S[j] = S[j - 1] + C[i][j - 1];
        }
        pq.push({ 0, i, X[i], 0, 0, 0, 0, 0 });
        sum += S[X[i]];
    }
    for (int i = 0; i < m + k + 5 && !pq.empty(); ++i) {
        node n = pq.top(); pq.pop();
        G[n.idx].push_back(n.val);
        if (!n.movC && n.cnt < Y[n.idx]) {
            pq.push({ n.val + C[n.idx][n.cnt], n.idx, n.cnt + 1, 0, 0, 0, 0, 0 });
        }
        if (!n.movL && 0 <= n.cnt - n.movC - 1 && n.cnt + n.movC < int(C[n.idx].size())) {
            pq.push({ n.val - C[n.idx][n.cnt - n.movC - 1] + C[n.idx][n.cnt + n.movC], n.idx, n.cnt, n.movC + 1, 0, 0, 0, 0 });
        }
        if (!n.movL && n.movC && 0 <= n.cnt - n.movC - 1) {
            pq.push({ n.val - C[n.idx][n.cnt - n.movC - 1] + C[n.idx][n.cnt - n.movC], n.idx, n.cnt, n.movC, 1, 0, n.cnt - n.movC - 1, -1 });
        }
        if (!n.movR && n.movC && n.cnt + n.movC < int(C[n.idx].size())) {
            pq.push({ n.val - C[n.idx][n.cnt + n.movC - 1] + C[n.idx][n.cnt + n.movC], n.idx, n.cnt, n.movC, n.movC + 1, 1, n.cnt + n.movC, int(C[n.idx].size()) });
        }
        if (n.movL && n.movL <= n.movC && n.movP < n.movV - 1) {
            pq.push({ n.val - C[n.idx][n.movV - 1] + C[n.idx][n.movV], n.idx, n.cnt, n.movC, n.movL, 0, n.movV - 1, n.movP });
        }
        if (n.movL && n.movL < n.movC && n.movV < n.cnt - n.movC + n.movL - 1) {
            pq.push({ n.val - C[n.idx][n.cnt - n.movC + n.movL - 1] + C[n.idx][n.cnt - n.movC + n.movL], n.idx, n.cnt, n.movC, n.movL + 1, 0, n.cnt - n.movC + n.movL - 1, n.movV });
        }
        if (n.movR && n.movR <= n.movC && n.movV + 1 < n.movP) {
            pq.push({ n.val - C[n.idx][n.movV] + C[n.idx][n.movV + 1], n.idx, n.cnt, n.movC, n.movC + 1, n.movR, n.movV + 1, n.movP });
        }
        if (n.movR && n.movR < n.movC && n.cnt + n.movC - n.movR < n.movV) {
            pq.push({ n.val - C[n.idx][n.cnt + n.movC - n.movR - 1] + C[n.idx][n.cnt + n.movC - n.movR], n.idx, n.cnt, n.movC, n.movC + 1, n.movR + 1, n.cnt + n.movC - n.movR, n.movV });
        }
    }
    --k, printf("%lld\n", sum);
    vector<vector<llong>> g;
    for (int i = 1; i <= m; ++i) {
        if (int(G[i].size()) <= 1) continue;
        for (int j = int(G[i].size()) - 1; j > 0; --j) G[i][j] -= G[i][j - 1];
        g.push_back(G[i]);
    }
    sort(g.begin(), g.end());
    priority_queue<pair<llong, pair<int, int>>> pq2;
    if (!g.empty()) pq2.emplace(-g[0][1], pair(0, 1));
    while (k && !pq2.empty()) {
        auto tp = pq2.top(); pq2.pop();
        --k, printf("%lld\n", sum - tp.first);
        auto [idx, cnt] = tp.second;
        if (idx + 1 < int(g.size()) && cnt == 1) {
            pq2.emplace(tp.first - g[idx + 1][1] + g[idx][1], pair(idx + 1, 1));
        }
        if (idx + 1 < int(g.size())) {
            pq2.emplace(tp.first - g[idx + 1][1], pair(idx + 1, 1));
        }
        if (cnt + 1 < int(g[idx].size())) {
            pq2.emplace(tp.first - g[idx][cnt + 1], pair(idx, cnt + 1));
        }
    }
    fail();
    return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 5 / 5
• Subtask 4: 5 / 5
• Subtask 5: 5 / 5