oj.uz

Submission #48412

# Submission time Handle Problem Language Result Execution time Memory
48412 2018-05-12T19:58:42 Z choikiwon Candies (JOI18_candies) C++17
100 / 100
 146 ms 65368 KB 
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

const int MN = 200010;

int N;
ll A[MN];
int pre[MN], nxt[MN];
priority_queue<pair<ll, int> > pq;

int main() {
    scanf("%d", &N);

    for(int i = 0; i < N; i++) {
        scanf("%lld", &A[i]);
    }
    for(int i = 0; i < N; i++) {
        pre[i] = i - 1;
        nxt[i] = i + 1;
        pq.push({ A[i], i });
    }

    ll sum = 0;
    for(int i = 1; i <= (N + 1) / 2; i++) {
        pair<ll, int> t = {-1, -1};
        while(!pq.empty()) {
            t = pq.top(); pq.pop();
            if(A[t.second] == t.first) break;
        }
        sum += t.first;
        printf("%lld\n", sum);

        A[t.second] = -A[t.second];
        bool ok = true;
        if(pre[t.second] != -1) {
            A[t.second] += A[ pre[t.second] ];
            A[ pre[t.second] ] = -1e18;
            pre[t.second] = pre[ pre[t.second] ];
            if(pre[t.second] != -1) nxt[ pre[t.second] ] = t.second;
        }
        else ok = false;
        if(nxt[t.second] != N) {
            A[t.second] += A[ nxt[t.second] ];
            A[ nxt[t.second] ] = -1e18;
            nxt[t.second] = nxt[ nxt[t.second] ];
            if(nxt[t.second] != N) pre[ nxt[t.second] ] = t.second;
        }
        else ok = false;
        if(ok) pq.push({ A[t.second], t.second });
        else A[t.second] = -1e18;
    }
}

Compilation message

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

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 504 KB Output is correct
2 Correct 5 ms 608 KB Output is correct
3 Correct 3 ms 608 KB Output is correct
4 Correct 3 ms 668 KB Output is correct
5 Correct 3 ms 748 KB Output is correct
6 Correct 3 ms 808 KB Output is correct
7 Correct 3 ms 824 KB Output is correct
8 Correct 3 ms 1100 KB Output is correct
9 Correct 3 ms 1100 KB Output is correct
10 Correct 3 ms 1100 KB Output is correct
11 Correct 3 ms 1100 KB Output is correct
12 Correct 3 ms 1100 KB Output is correct
13 Correct 3 ms 1212 KB Output is correct
14 Correct 3 ms 1212 KB Output is correct
15 Correct 3 ms 1212 KB Output is correct
16 Correct 3 ms 1276 KB Output is correct
17 Correct 3 ms 1276 KB Output is correct
18 Correct 3 ms 1276 KB Output is correct
19 Correct 3 ms 1276 KB Output is correct
20 Correct 3 ms 1276 KB Output is correct

Subtask #2
92.0 / 92.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 504 KB Output is correct
2 Correct 5 ms 608 KB Output is correct
3 Correct 3 ms 608 KB Output is correct
4 Correct 3 ms 668 KB Output is correct
5 Correct 3 ms 748 KB Output is correct
6 Correct 3 ms 808 KB Output is correct
7 Correct 3 ms 824 KB Output is correct
8 Correct 3 ms 1100 KB Output is correct
9 Correct 3 ms 1100 KB Output is correct
10 Correct 3 ms 1100 KB Output is correct
11 Correct 3 ms 1100 KB Output is correct
12 Correct 3 ms 1100 KB Output is correct
13 Correct 3 ms 1212 KB Output is correct
14 Correct 3 ms 1212 KB Output is correct
15 Correct 3 ms 1212 KB Output is correct
16 Correct 3 ms 1276 KB Output is correct
17 Correct 3 ms 1276 KB Output is correct
18 Correct 3 ms 1276 KB Output is correct
19 Correct 3 ms 1276 KB Output is correct
20 Correct 3 ms 1276 KB Output is correct
21 Correct 136 ms 10880 KB Output is correct
22 Correct 143 ms 12808 KB Output is correct
23 Correct 146 ms 14764 KB Output is correct
24 Correct 110 ms 16556 KB Output is correct
25 Correct 102 ms 18316 KB Output is correct
26 Correct 110 ms 20156 KB Output is correct
27 Correct 119 ms 22024 KB Output is correct
28 Correct 116 ms 23976 KB Output is correct
29 Correct 115 ms 26200 KB Output is correct
30 Correct 133 ms 27972 KB Output is correct
31 Correct 125 ms 29860 KB Output is correct
32 Correct 112 ms 31848 KB Output is correct
33 Correct 126 ms 33620 KB Output is correct
34 Correct 126 ms 35400 KB Output is correct
35 Correct 126 ms 37112 KB Output is correct
36 Correct 139 ms 39028 KB Output is correct
37 Correct 139 ms 40960 KB Output is correct
38 Correct 136 ms 42872 KB Output is correct
39 Correct 110 ms 44712 KB Output is correct
40 Correct 106 ms 46444 KB Output is correct
41 Correct 104 ms 48300 KB Output is correct
42 Correct 116 ms 50196 KB Output is correct
43 Correct 115 ms 52152 KB Output is correct
44 Correct 114 ms 54112 KB Output is correct
45 Correct 117 ms 56140 KB Output is correct
46 Correct 116 ms 58116 KB Output is correct
47 Correct 114 ms 59992 KB Output is correct
48 Correct 129 ms 61700 KB Output is correct
49 Correct 126 ms 63504 KB Output is correct
50 Correct 143 ms 65368 KB Output is correct