Submission #893266

#	Time	Username	Problem	Language	Result	Execution time	Memory
893266		box	Candies (JOI18_candies)	C++17	0 / 100	1 ms	344 KiB

candies

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

#define ar array
#define sz(v) int(std::size(v))
using i64 = long long;

const int N = 200000;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N;
    cin >> N;
    vector<int> A(N);
    for (int &x : A) cin >> x;
    priority_queue<pair<i64, int>> paths;
    vector<int> L(N), R(N), done(N);
    for (int i = 0; i < N; i++) {
        L[i] = i - 1, R[i] = i + 1;
        paths.push({A[i], i});
    }
    int take = (N + 1) / 2;
    i64 total_cost = 0;
    for (int rep = 0; rep < take; rep++) {
        while (sz(paths) && done[paths.top().second]) paths.pop();
        assert(sz(paths));
        auto [cost, i] = paths.top(); paths.pop();
        total_cost += cost;
        cout << total_cost << '\n';
        A[i] = (L[i] < 0 ? 0 : A[L[i]]) + (R[i] >= N ? 0 : A[R[i]]) - A[i];
        if (L[i] >= 0) {
            done[L[i]] = 1;
            int u = L[L[i]];
            if (u >= 0) R[u] = i;
            L[i] = u;
        }
        if (R[i] < N) {
            done[R[i]] = 1;
            int u = R[R[i]];
            if (u < N) L[u] = i;
            R[i] = u;
        }
        paths.push({A[i], i});
    }
}

• Subtask 1: 0 / 8
• Subtask 2: 0 / 92