Submission #98193

#	Time	Username	Problem	Language	Result	Execution time	Memory
98193		onjo0127	Candies (JOI18_candies)	C++11	100 / 100	189 ms	10488 KiB

candies

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

long long A[200009];
int L[200009], R[200009];
bool chk[200009];

int main() {
    int N; scanf("%d",&N);
    priority_queue<pair<long long, int> > pq;
    for(int i=1; i<=N; i++) {
        scanf("%d",&A[i]);
        pq.push({A[i], i});
        L[i] = i-1; R[i] = i+1;
    }
    pq.push({-1LL * 1e18, 0}); R[0] = 1; A[0] = -1LL * 1e18;
    pq.push({-1LL * 1e18, N+1}); L[N+1] = N; A[N+1] = -1LL * 1e18;
    long long ans = 0;
    for(int i=1; i<=(N+1)/2; i++) {
        long long v; int id;
        while(1) {
            tie(v, id) = pq.top(); pq.pop();
            if(!chk[id]) break;
        }
        ans += v; printf("%lld\n",ans);
        A[id] = A[L[id]] + A[R[id]] - A[id];
        pq.push({A[id], id});
        chk[L[id]] = chk[R[id]] = 1;
        L[id] = L[L[id]]; R[id] = R[R[id]];
        R[L[id]] = id; L[R[id]] = id;
    }
    return 0;
}

Compilation message (stderr)

candies.cpp: In function 'int main()':
candies.cpp:12:25: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'long long int*' [-Wformat=]
         scanf("%d",&A[i]);
                    ~~~~~^
candies.cpp:9:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     int N; scanf("%d",&N);
            ~~~~~^~~~~~~~~
candies.cpp:12:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&A[i]);
         ~~~~~^~~~~~~~~~~~

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