Submission #227496

#	Time	Username	Problem	Language	Result	Execution time	Memory
227496		MKopchev	Candies (JOI18_candies)	C++14	100 / 100	175 ms	12936 KiB

candies

#include<bits/stdc++.h>
using namespace std;
const int nmax=4e5+42;

int n;

int inp[nmax];

bool blocked[nmax];

int left_active[nmax],right_active[nmax];

priority_queue< pair<long long/*gain*/,int/*id*/> > pq;

long long would_add[nmax];

int main()
{
    scanf("%i",&n);

    for(int i=1;i<=n;i++)
    {
        scanf("%i",&inp[i]);

        would_add[i]=inp[i];

        left_active[i]=i-1;
        right_active[i]=i+1;
        pq.push({inp[i],i});
    }

    would_add[0]=-1e18;
    would_add[n+1]=-1e18;

    left_active[0]=0;
    right_active[0]=1;

    left_active[n+1]=n;
    right_active[n+1]=n+1;

    long long outp=0;

    for(int j=1;j<=(n+1)/2;j++)
    {
        while(blocked[pq.top().second])pq.pop();

        /*
        cout<<pq.size()<<" "<<pq.top().first<<" "<<pq.top().second<<endl;

        for(int p=1;p<=n+1+j;p++)cout<<p<<" "<<blocked[p]<<" "<<left_active[p]<<" "<<right_active[p]<<endl;

        for(int p=1;p<=n+1+j;p++)
            if(blocked[p]==0)cout<<p<<" -> "<<would_add[p]<<endl;

        cout<<"---"<<endl;
        */

        outp+=pq.top().first;

        int id=pq.top().second;

        pq.pop();

        int new_id=n+1+j;

        would_add[new_id]=would_add[left_active[id]]+would_add[right_active[id]]-would_add[id];

        //cout<<j<<" -> "<<new_id<<" "<<would_add[new_id]<<" id= "<<id<<endl;

        pq.push({would_add[new_id],new_id});

        blocked[left_active[id]]=1;
        blocked[right_active[id]]=1;
        blocked[id]=1;

        left_active[new_id]=left_active[left_active[id]];

        right_active[left_active[left_active[id]]]=new_id;

        right_active[new_id]=right_active[right_active[id]];

        left_active[right_active[right_active[id]]]=new_id;

        printf("%lld\n",outp);
    }
    return 0;
}

Compilation message (stderr)

candies.cpp: In function 'int main()':
candies.cpp:19:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%i",&n);
     ~~~~~^~~~~~~~~
candies.cpp:23:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%i",&inp[i]);
         ~~~~~^~~~~~~~~~~~~~

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