Submission #45133

#	Time	Username	Problem	Language	Result	Execution time	Memory
45133		ikura355	Candies (JOI18_candies)	C++14	100 / 100	197 ms	13320 KiB

candies

#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 5;
struct node {
    int x,y;
    long long val;
    node(int _x = 0, int _y = 0, long long _val = 0) {
        x = _x; y = _y; val = _val;
    }
    bool operator < (node a) const {
        return a.val>val;
    }
};
int n;
long long a[maxn];
int l[maxn], r[maxn];
long long sum[maxn], lval[maxn], rval[maxn];
priority_queue<node> heap;
int main() {
    scanf("%d",&n); n += 2;
    for(int i=2;i<=n-1;i++) scanf("%lld",&a[i]);
    a[1] = a[n] = -1e16;
    for(int i=1;i<=n;i++) sum[i] = sum[i-1] + a[i];
    for(int i=0;i<=n;i++) {
        l[i] = r[i] = -1;
        if(i!=0) l[i] = i-1, lval[i] = sum[i]-sum[i-1];
        if(i!=n) r[i] = i+1, rval[i] = sum[i+1]-sum[i];
        if(i) heap.push(node(i-1,i,sum[i]-sum[i-1]));
    }
    int cur = (n-2+1)/2;
    long long ans = 0;
    while(!heap.empty() && cur) {
        node t = heap.top(); heap.pop();
        int x = t.x, y = t.y;
        long long val = t.val;
        if(r[x]!=y || l[y]!=x) continue;
        ans += val;
        int L = l[x], R = r[y];
        if(L!=-1 && R!=-1) {
            long long nval = lval[x] + rval[y] - val;
            r[L] = R; l[R] = L;
            rval[L] = lval[R] = nval;
            heap.push(node(L,R,nval));
        }
        printf("%lld\n",ans);
        cur--;
    }
}

Compilation message (stderr)

candies.cpp: In function 'int main()':
candies.cpp:20:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&n); n += 2;
     ~~~~~^~~~~~~~~
candies.cpp:21:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i=2;i<=n-1;i++) scanf("%lld",&a[i]);
                             ~~~~~^~~~~~~~~~~~~~

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