#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 2e5 + 10;
const ll inf = 0x3f3f3f3f3f3f3f3f;
int n, a[N];
set<pair<ll, int>> val;
set<pair<int, ll>> pos;
void add(int i, ll v) {
val.emplace(v, i);
pos.emplace(i, v);
}
void rem(int i, ll v) {
val.erase(val.find({v, i}));
pos.erase(pos.find({i, v}));
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
for (int i = 1; i <= n; i++) add(i, a[i]);
add(0, -inf); add(n + 1, -inf);
ll ans = 0;
for (int i = 0; i < (n + 1) / 2; i++) {
auto it = prev(val.end());
pair<ll, int> f = *it;
ans += f.first;
auto ti = pos.lower_bound({f.second, -inf});
printf("%lld\n", ans);
pair<int, ll> x = *prev(ti);
pair<int, ll> y = *ti;
pair<int, ll> z = *next(ti);
rem(x.first, x.second);
rem(y.first, y.second);
rem(z.first, z.second);
add(y.first, x.second + z.second - y.second);
}
return 0;
}
Compilation message
candies.cpp: In function 'int main()':
candies.cpp:18:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
18 | scanf("%d", &n);
| ~~~~~^~~~~~~~~~
candies.cpp:19:39: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
19 | for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
| ~~~~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
596 KB |
Output is correct |
| 2 |
Correct |
2 ms |
520 KB |
Output is correct |
| 3 |
Correct |
2 ms |
596 KB |
Output is correct |
| 4 |
Correct |
3 ms |
580 KB |
Output is correct |
| 5 |
Correct |
2 ms |
576 KB |
Output is correct |
| 6 |
Correct |
2 ms |
580 KB |
Output is correct |
| 7 |
Correct |
3 ms |
580 KB |
Output is correct |
| 8 |
Correct |
2 ms |
576 KB |
Output is correct |
| 9 |
Correct |
2 ms |
596 KB |
Output is correct |
| 10 |
Correct |
2 ms |
596 KB |
Output is correct |
| 11 |
Correct |
2 ms |
596 KB |
Output is correct |
| 12 |
Correct |
2 ms |
596 KB |
Output is correct |
| 13 |
Correct |
2 ms |
576 KB |
Output is correct |
| 14 |
Correct |
3 ms |
596 KB |
Output is correct |
| 15 |
Correct |
3 ms |
596 KB |
Output is correct |
| 16 |
Correct |
3 ms |
568 KB |
Output is correct |
| 17 |
Correct |
2 ms |
584 KB |
Output is correct |
| 18 |
Correct |
3 ms |
596 KB |
Output is correct |
| 19 |
Correct |
2 ms |
580 KB |
Output is correct |
| 20 |
Correct |
2 ms |
596 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
596 KB |
Output is correct |
| 2 |
Correct |
2 ms |
520 KB |
Output is correct |
| 3 |
Correct |
2 ms |
596 KB |
Output is correct |
| 4 |
Correct |
3 ms |
580 KB |
Output is correct |
| 5 |
Correct |
2 ms |
576 KB |
Output is correct |
| 6 |
Correct |
2 ms |
580 KB |
Output is correct |
| 7 |
Correct |
3 ms |
580 KB |
Output is correct |
| 8 |
Correct |
2 ms |
576 KB |
Output is correct |
| 9 |
Correct |
2 ms |
596 KB |
Output is correct |
| 10 |
Correct |
2 ms |
596 KB |
Output is correct |
| 11 |
Correct |
2 ms |
596 KB |
Output is correct |
| 12 |
Correct |
2 ms |
596 KB |
Output is correct |
| 13 |
Correct |
2 ms |
576 KB |
Output is correct |
| 14 |
Correct |
3 ms |
596 KB |
Output is correct |
| 15 |
Correct |
3 ms |
596 KB |
Output is correct |
| 16 |
Correct |
3 ms |
568 KB |
Output is correct |
| 17 |
Correct |
2 ms |
584 KB |
Output is correct |
| 18 |
Correct |
3 ms |
596 KB |
Output is correct |
| 19 |
Correct |
2 ms |
580 KB |
Output is correct |
| 20 |
Correct |
2 ms |
596 KB |
Output is correct |
| 21 |
Correct |
500 ms |
29520 KB |
Output is correct |
| 22 |
Correct |
488 ms |
29516 KB |
Output is correct |
| 23 |
Correct |
488 ms |
29532 KB |
Output is correct |
| 24 |
Correct |
242 ms |
29460 KB |
Output is correct |
| 25 |
Correct |
227 ms |
29392 KB |
Output is correct |
| 26 |
Correct |
224 ms |
29388 KB |
Output is correct |
| 27 |
Correct |
254 ms |
29516 KB |
Output is correct |
| 28 |
Correct |
257 ms |
29516 KB |
Output is correct |
| 29 |
Correct |
257 ms |
29544 KB |
Output is correct |
| 30 |
Correct |
256 ms |
29532 KB |
Output is correct |
| 31 |
Correct |
276 ms |
29560 KB |
Output is correct |
| 32 |
Correct |
266 ms |
29440 KB |
Output is correct |
| 33 |
Correct |
362 ms |
29316 KB |
Output is correct |
| 34 |
Correct |
391 ms |
29276 KB |
Output is correct |
| 35 |
Correct |
385 ms |
29384 KB |
Output is correct |
| 36 |
Correct |
492 ms |
29436 KB |
Output is correct |
| 37 |
Correct |
486 ms |
29564 KB |
Output is correct |
| 38 |
Correct |
535 ms |
29424 KB |
Output is correct |
| 39 |
Correct |
242 ms |
29292 KB |
Output is correct |
| 40 |
Correct |
236 ms |
29304 KB |
Output is correct |
| 41 |
Correct |
251 ms |
29388 KB |
Output is correct |
| 42 |
Correct |
251 ms |
29452 KB |
Output is correct |
| 43 |
Correct |
244 ms |
29508 KB |
Output is correct |
| 44 |
Correct |
244 ms |
29460 KB |
Output is correct |
| 45 |
Correct |
266 ms |
29536 KB |
Output is correct |
| 46 |
Correct |
257 ms |
29548 KB |
Output is correct |
| 47 |
Correct |
272 ms |
29644 KB |
Output is correct |
| 48 |
Correct |
385 ms |
29368 KB |
Output is correct |
| 49 |
Correct |
351 ms |
29336 KB |
Output is correct |
| 50 |
Correct |
345 ms |
29240 KB |
Output is correct |
