제출 #1162787

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1162787		Hamed_Ghaffari	Candies (JOI18_candies)	C++20	100 / 100	94 ms	8520 KiB

candies

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

using ll = long long;

const int MXN = 2e5+5;

int n;
int lf[MXN], rg[MXN];
ll val[MXN];
priority_queue<pair<ll, int>> pq;
bool mark[MXN];

int32_t main() {
    cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
    cin >> n;
    for(int i=1; i<=n; i++) {
        cin >> val[i];
        pq.push({val[i], i});
        lf[i] = i-1;
        rg[i] = i+1;
    }
    val[0] = val[n+1] = -1e17;
    ll ans=0;
    int cnt=0;
    while(cnt<(n+1>>1)) {
        int i = pq.top().second;
        pq.pop();
        if(mark[i]) continue;
        ans += val[i];
        mark[lf[i]] = mark[rg[i]] = 1;
        pq.push({val[i] = val[lf[i]]+val[rg[i]]-val[i], i});
        lf[i] = lf[lf[i]];
        rg[i] = rg[rg[i]];
        lf[rg[i]] = rg[lf[i]] = i;
        cout << ans << '\n';
        cnt++;
    }
}

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