Submission #1162623

#	Time	Username	Problem	Language	Result	Execution time	Memory
1162623		VMaksimoski008	Candies (JOI18_candies)	C++20	100 / 100	100 ms	9092 KiB

candies

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

signed main() {
    int n; cin >> n;
    vector<ll> a(n+2, -1e18);
    for(int i=1; i<=n; i++) cin >> a[i];

    vector<int> L(n+2), R(n+2), vis(n+1);
    for(int i=1; i<=n; i++) {
        L[i] = i - 1;
        R[i] = i + 1;
    }

    priority_queue<pair<ll, ll> > pq;
    for(int i=1; i<=n; i++) pq.push({ a[i], i });

    ll ans = 0;
    for(int i=1; i<=(n+1)/2; i++) {
        while(!pq.empty() && vis[pq.top().second]) pq.pop();
        assert(!pq.empty());
        auto [val, p] = pq.top(); pq.pop();
        ans += val;
        vis[L[p]] = vis[R[p]] = 1;
        pq.push({ a[p] = a[L[p]] + a[R[p]] - a[p], p });
        L[p] = L[L[p]];
        R[p] = R[R[p]];
        R[L[p]] = p;
        L[R[p]] = p;
        cout << ans << '\n';
    }
}

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