oj.uz

Submission #1088088

# Submission time Handle Problem Language Result Execution time Memory
1088088 2024-09-13T20:30:39 Z DobromirAngelov Candies (JOI18_candies) C++14
0 / 100
 1 ms 604 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 604 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 92.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 604 KB Output isn't correct
2 Halted 0 ms 0 KB -