Submission #617677

#	Time	Username	Problem	Language	Result	Execution time	Memory
617677		bebra	Candies (JOI18_candies)	C++17	100 / 100	113 ms	10228 KiB

candies

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

#define dbg(x) cerr << #x << ": " << x << endl;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<long long> a(n + 2);
    vector<int> l(n + 2);
    vector<int> r(n + 2);
    priority_queue<pair<long long, int>> pq;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        l[i] = i - 1;
        r[i] = i + 1;
        pq.emplace(a[i], i);
    }
    
    const long long MINUS_INF = -1e15;
    a[0] = MINUS_INF;
    a[n + 1] = MINUS_INF;

    l[n + 1] = n;
    r[0] = 1;

    long long curr_ans = 0;
    vector<bool> used(n + 2);
    for (int j = 1; j <= (n + 1) / 2; ++j) {
        auto [value, i] = pq.top();
        while (used[i]) {
            pq.pop();
            tie(value, i) = pq.top();
        }
        pq.pop();

        curr_ans += value;
        cout << curr_ans << '\n';

        a[i] = a[l[i]] + a[r[i]] - a[i];
        used[l[i]] = true;
        used[r[i]] = true;
        pq.emplace(a[i], i);

        l[i] = l[l[i]];
        r[l[i]] = i;

        r[i] = r[r[i]];
        l[r[i]] = i;
    }
    
    return 0;
}

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