oj.uz

Submission #877827

# Submission time Handle Problem Language Result Execution time Memory
877827 2023-11-23T16:42:22 Z coldEr66 Candies (JOI18_candies) C++14
100 / 100
 71 ms 14020 KB 
#ifndef Yamada
#define Yamada
#include Yamada __FILE__ Yamada

const int maxn = 2e5+5;

int pre[maxn], nxt[maxn], a[maxn], era[maxn];

int del(int x) {
    nxt[pre[x]] = nxt[x];
    pre[nxt[x]] = pre[x];
    era[x] = 1;
    return a[x];
}
void solve() {
    int n; cin >> n;
    MaxHeap<pii> pq;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        pre[i] = i-1, nxt[i] = i+1;
        pq.emplace(a[i], i);
    }
    nxt[n-1] = -1;

    int ans = 0;
    for (int i = 1; i <= (n+1) / 2; ++i) {
        int curw, idx;
        while (SZ(pq)) {
            auto [tw, ti] = pq.top(); pq.pop();
            if (!era[ti]) {
                curw = tw, idx = ti;
                break;
            }
        }

        ans += curw;
        int nxtw = 0, cnt = 0;
        if (pre[idx] != -1) {
            nxtw += del(pre[idx]);
            ++cnt;
        }
        if (nxt[idx] != -1) {
            nxtw += del(nxt[idx]);
            ++cnt;
        }
        nxtw -= curw;
        
        a[idx] = nxtw;
        if (cnt == 2) pq.emplace(a[idx], idx);
        else del(idx);

        print(ans);
    }
}

signed main() {
    IOS();
    int t = 1; // cin >> t;
    for (int i=1;i<=t;++i) solve();
    return 0;
}

#else

#ifdef local 
#define _GLIBCXX_DEBUG 1
#endif
#pragma GCC optimize ("Ofast", "unroll-loops")
#include <bits/stdc++.h>
using namespace std;

#define int int64_t
#define double __float80
using pii = pair<int, int>;
template <typename T> using MaxHeap = std::priority_queue<T>;
template <typename T> using MinHeap = std::priority_queue<T, vector<T>, greater<T>>;

#define SZ(a) ((int)(a).size())
#define ALL(a) begin(a), end(a)
#define RALL(a) rbegin(a), rend(a)
#define ee emplace
#define eb emplace_back
#define ef emplace_front
#define pb pop_back
#define pf pop_front
// #define X first
// #define Y second

#ifdef local
#define IOS() void()
#define debug(...) \
    fprintf(stderr, "\e[1;93m"), \
    fprintf(stderr, "At [%s], line %d: (%s) = ", __FUNCTION__, __LINE__, #__VA_ARGS__), \
    _do(__VA_ARGS__), \
    fprintf(stderr, "\e[0m")
template <typename T> void _do(T &&_t) {cerr << _t << '\n';}
template <typename T, typename ...U> void _do(T &&_t, U &&..._u) {cerr << _t << ", ", _do(_u...);}
#define print(...) \
    fprintf(stderr, "\e[1;96m"), \
    _P(__VA_ARGS__), \
    fprintf(stderr, "\e[0m")
#else
#define IOS() ios_base::sync_with_stdio(0); cin.tie(0)
#define debug(...) void()
#define print(...) _P(__VA_ARGS__)
#define endl '\n'
#endif

template <typename U, typename V> bool chmin(U &u, V v) {return u > v ? u = v, 1 : 0;}
template <typename U, typename V> bool chmax(U &u, V v) {return u < v ? u = v, 1 : 0;}

template <typename T> void _P(T &&_x) {cout << _x << '\n';}
template <typename T, typename ...S> void _P(T &&_x, S &&..._t) {cout << _x << " "; _P(_t...);}

#endif

Compilation message

candies.cpp: In function 'void solve()':
candies.cpp:29:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   29 |             auto [tw, ti] = pq.top(); pq.pop();
      |                  ^
candies.cpp:36:13: warning: 'curw' may be used uninitialized in this function [-Wmaybe-uninitialized]
   36 |         ans += curw;
      |         ~~~~^~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4700 KB Output is correct
3 Correct 1 ms 4700 KB Output is correct
4 Correct 1 ms 4700 KB Output is correct
5 Correct 1 ms 4700 KB Output is correct
6 Correct 1 ms 4700 KB Output is correct
7 Correct 1 ms 4700 KB Output is correct
8 Correct 1 ms 4700 KB Output is correct
9 Correct 1 ms 4700 KB Output is correct
10 Correct 2 ms 4700 KB Output is correct
11 Correct 1 ms 4700 KB Output is correct
12 Correct 1 ms 4672 KB Output is correct
13 Correct 1 ms 4700 KB Output is correct
14 Correct 1 ms 4700 KB Output is correct
15 Correct 1 ms 4700 KB Output is correct
16 Correct 1 ms 4696 KB Output is correct
17 Correct 2 ms 4700 KB Output is correct
18 Correct 1 ms 4700 KB Output is correct
19 Correct 1 ms 4952 KB Output is correct
20 Correct 1 ms 4700 KB Output is correct

Subtask #2
92.0 / 92.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4700 KB Output is correct
3 Correct 1 ms 4700 KB Output is correct
4 Correct 1 ms 4700 KB Output is correct
5 Correct 1 ms 4700 KB Output is correct
6 Correct 1 ms 4700 KB Output is correct
7 Correct 1 ms 4700 KB Output is correct
8 Correct 1 ms 4700 KB Output is correct
9 Correct 1 ms 4700 KB Output is correct
10 Correct 2 ms 4700 KB Output is correct
11 Correct 1 ms 4700 KB Output is correct
12 Correct 1 ms 4672 KB Output is correct
13 Correct 1 ms 4700 KB Output is correct
14 Correct 1 ms 4700 KB Output is correct
15 Correct 1 ms 4700 KB Output is correct
16 Correct 1 ms 4696 KB Output is correct
17 Correct 2 ms 4700 KB Output is correct
18 Correct 1 ms 4700 KB Output is correct
19 Correct 1 ms 4952 KB Output is correct
20 Correct 1 ms 4700 KB Output is correct
21 Correct 67 ms 13280 KB Output is correct
22 Correct 70 ms 13504 KB Output is correct
23 Correct 69 ms 14020 KB Output is correct
24 Correct 57 ms 13248 KB Output is correct
25 Correct 56 ms 13248 KB Output is correct
26 Correct 57 ms 13248 KB Output is correct
27 Correct 64 ms 13248 KB Output is correct
28 Correct 68 ms 13412 KB Output is correct
29 Correct 65 ms 13756 KB Output is correct
30 Correct 65 ms 13232 KB Output is correct
31 Correct 64 ms 13244 KB Output is correct
32 Correct 65 ms 13236 KB Output is correct
33 Correct 70 ms 13132 KB Output is correct
34 Correct 69 ms 12996 KB Output is correct
35 Correct 66 ms 13756 KB Output is correct
36 Correct 70 ms 13364 KB Output is correct
37 Correct 71 ms 13660 KB Output is correct
38 Correct 67 ms 13236 KB Output is correct
39 Correct 57 ms 13248 KB Output is correct
40 Correct 62 ms 13244 KB Output is correct
41 Correct 57 ms 14016 KB Output is correct
42 Correct 65 ms 13268 KB Output is correct
43 Correct 64 ms 13240 KB Output is correct
44 Correct 70 ms 13248 KB Output is correct
45 Correct 65 ms 13192 KB Output is correct
46 Correct 65 ms 13248 KB Output is correct
47 Correct 64 ms 13240 KB Output is correct
48 Correct 66 ms 13760 KB Output is correct
49 Correct 66 ms 12992 KB Output is correct
50 Correct 69 ms 12992 KB Output is correct