Submission #1088088

#	Time	Username	Problem	Language	Result	Execution time	Memory
1088088		DobromirAngelov	Candies (JOI18_candies)	C++14	0 / 100	1 ms	604 KiB

candies

#include<bits/stdc++.h>
#define endl '\n'
#define fi first
#define se second

using namespace std;

const int MAXN=2e5+5;

int n;
long long a[MAXN];
int l[MAXN], r[MAXN];
priority_queue<pair<long long,int> > pq;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];

    for(int i=1;i<=n;i++)
    {
        l[i]=r[i]=i;
        pq.push({a[i],i});
    }

    long long ans=0;
    for(int i=1;i<=(n+1)/2;i++)
    {
        auto cur=pq.top();
        pq.pop();
        if(a[cur.se]!=cur.fi) {i--; continue;}
        int le=l[cur.se]-1;
        int ri=r[cur.se]+1;

        ans+=cur.fi;
        cout<<ans<<endl;

        l[le]=l[ri]=le;
        r[le]=r[ri]=ri;
        a[le]=a[ri]=a[le]+a[ri]-cur.fi;
        if(le>=1 && ri<=n) pq.push({a[le],le});
    }

    return 0;
}

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