# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1124237 | kh0i | Candies (JOI18_candies) | C++20 | 1 ms | 576 KiB |
#include "bits/stdc++.h"
using namespace std;
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...)
#endif
using ll = long long;
using pii = pair<int, int>;
#define F first
#define S second
#define sz(x) (int)((x).size())
#define all(x) (x).begin(), (x).end()
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll get_rand(ll l, ll r) {
assert(l <= r);
return uniform_int_distribution<ll> (l, r)(rng);
}
const int N = 2e5 + 3;
int n, nxt[N], pre[N];
ll a[N], res[N];
bool del[N];
void solve(){
cin >> n;
for(int i = 1; i <= n; ++i){
cin >> a[i];
nxt[i] = i + 1;
pre[i] = i - 1;
}
nxt[0] = 1, pre[n + 1] = n;
priority_queue<pair<ll, int>> pq;
for(int i = 1; i <= n; ++i)
pq.push(make_pair(a[i], i));
int cnt = 0;
ll cur = 0;
while(!pq.empty() and cnt < (n + 1) / 2){
pair<ll, int> x = pq.top();
pq.pop();
int id = x.S;
if(del[id])
continue;
cur += x.F;
++cnt;
del[pre[id]] = del[nxt[id]] = 1;
res[cnt] = cur;
if(pre[id] == 0 or nxt[id] == n + 1)
continue;
a[id] = a[pre[id]] + a[nxt[id]] - x.F;
pq.push({a[id], id});
nxt[id] = nxt[nxt[id]];
pre[id] = pre[pre[id]];
nxt[pre[id]] = pre[nxt[id]] = id;
}
for(int i = 1; i <= cnt; ++i)
cout << res[i] << "\n";
}
int32_t main() {
cin.tie(nullptr)->sync_with_stdio(0);
#define task "troll"
if(fopen(task".inp", "r")){
freopen(task".inp", "r", stdin);
freopen(task".out", "w", stdout);
}
int test = 1;
// cin >> test;
for(int i = 1; i <= test; ++i){
// cout << "Case #" << i << ": ";
solve();
}
#ifdef LOCAL
cerr << "\n[Time]: " << 1000.0 * clock() / CLOCKS_PER_SEC << " ms.\n";
#endif
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |