#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
candies.cpp: In function 'void solve()':
candies.cpp:36:13: warning: 'curw' may be used uninitialized in this function [-Wmaybe-uninitialized]
36 | ans += curw;
| ~~~~^~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
4696 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
4696 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
