Submission #1240229

#	Time	Username	Problem	Language	Result	Execution time	Memory
1240229		caterpillow	Candies (JOI18_candies)	C++17	100 / 100	210 ms	21208 KiB

candies

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

int main() {
    cin.tie(0)->sync_with_stdio(0);
    
    int n;
    cin >> n;
    vector<ll> a(n);
    for (ll &x : a) cin >> x;

    vector<vector<ll>> pfx(2, vector<ll>(n + 1));
    for (int i = 0; i < n; i++) pfx[i % 2][i + 1] = a[i];
    for (int i = 0; i < 2; i++) {
        for (int j = 0; j < n; j++) {
            pfx[i][j + 1] += pfx[i][j];
        }
    }
    auto sum_seg = [&] (int l, int r) {
        return pfx[l % 2][r] - pfx[l % 2][l];
    };

    set<int> segs;
    for (int i = -1; i <= n + 1; i++) segs.insert(i);
    using t3 = tuple<ll, int, int>; // gain, l, r
    priority_queue<t3> pq;
    for (int i = 0; i < n; i++) pq.push({a[i], i, i + 1});

    ll ans = 0;
    for (int _ = 1; _ <= (n + 1) / 2; _++) {
        while (true) {
            auto [gain, l, r] = pq.top(); pq.pop();
            auto lit = segs.find(l);
            auto rit = segs.find(r);
            if (lit == segs.end() || rit == segs.end()) continue;
            ans += gain;
            if (lit != segs.begin()) segs.erase(lit--);
            if (next(rit) != segs.end()) segs.erase(rit++);
            if (*lit >= 0 && *rit <= n)
                pq.push({sum_seg(*lit, *rit) - sum_seg(*lit + 1, *rit - 1), *lit, *rit});
            break;
        }
        cout << ans << '\n';
    }
}

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