Submission #48476

#	Time	Username	Problem	Language	Result	Execution time	Memory
48476		yp155136	Candies (JOI18_candies)	C++14	100 / 100	139 ms	20532 KiB

candies

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

typedef long long LL;
typedef pair<LL,LL> pii;

#define F first
#define S second

const int N = 200006;
const LL INF = (1LL<<40);

bool vis[N];
LL cost[N];

int lc[N];
int rc[N];

int main ()
{
    int n;
    scanf("%d",&n);
    priority_queue<pii> pq;
    for (int i=1;n>=i;i++)
    {
        scanf("%lld",&cost[i]);
        lc[i] = i-1;
        rc[i] = i+1;
        pq.push(make_pair(cost[i],i));
    }
    cost[0] = cost[n+1] = -INF;
    LL tot=0;
    int cnt=(n+1)/2;
    while (!pq.empty())
    {
        pii p=pq.top();
        pq.pop();
        if (vis[p.S]) continue;
        tot += p.F;
        LL newcost = cost[ lc[p.S] ] + cost[ rc[p.S] ] - cost[p.S];
        vis[ lc[p.S] ] = vis[ rc[p.S] ] = true;
        lc[p.S] = lc[ lc[p.S] ];
        rc[p.S] = rc[ rc[p.S] ];
        rc[ lc[p.S] ] = p.S;
        lc[ rc[p.S] ] = p.S;
        cost[p.S] = newcost;
        printf("%lld\n",tot);
        --cnt;
        pq.push(make_pair(cost[p.S],p.S));
        if (!cnt) break;
    }
}

Compilation message (stderr)

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

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