Submission #877824

#	Time	Username	Problem	Language	Result	Execution time	Memory
877824		coldEr66	Candies (JOI18_candies)	C++17	0 / 100	1 ms	4696 KiB

candies

#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);

        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 (stderr)

candies.cpp: In function 'void solve()':
candies.cpp:36:13: warning: 'curw' may be used uninitialized in this function [-Wmaybe-uninitialized]
   36 |         ans += curw;
      |         ~~~~^~~~~~~

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