oj.uz

Submission #45130

# Submission time Handle Problem Language Result Execution time Memory
45130 2018-04-11T12:16:25 Z ikura355 Candies (JOI18_candies) C++14
0 / 100
 3 ms 504 KB 
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e3 + 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);
    for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
    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]));
    }
    long long ans = 0, cur = (n+1)/2;
    while(!heap.empty() && cur) {
        node t = heap.top(); heap.pop();
        int x = t.x, y = t.y, 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

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);
     ~~~~~^~~~~~~~~
candies.cpp:21:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
                           ~~~~~^~~~~~~~~~~~~~

Subtask #1
0 / 8.0

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

Subtask #2
0 / 92.0

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