#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
#pragma GCC optimize ("Ofast")
#pragma GCC optimization ("unroll-loops, no-stack-protector")
#pragma GCC target ("avx")
#pragma GCC target ("avx2")
#pragma GCC target ("fma")
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define ll long long
#define ull unsigned long long
#define ld long double
#define pii pair <int, int>
#define pll pair <ll, ll>
#define pci pair <char, int>
#define pld pair <ld, ld>
#define ppld pair <pld, pld>
#define ppll pair <pll, pll>
#define pldl pair <ld, ll>
#define vll vector <ll>
#define vvll vector <vll>
#define vpll vector <pll>
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define mll map <ll, ll>
#define fastmap gp_hash_table
#define cd complex <double>
#define vcd vector <cd>
#define PI 3.14159265358979
#define ordered_set tree <ll, null_type, less <ll>, rb_tree_tag, tree_order_statistics_node_update>
#pragma 03
using namespace std;
using namespace __gnu_pbds;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
const ll INF = 1e18;
ll a[200005];
set <pll> choices;
ll l[200005], r[200005];
int main(){
fastio;
ll n; cin >> n;
a[0] = a[n + 1] = -INF;
for (ll i = 1; i <= n; i++){
cin >> a[i]; l[i] = i - 1; r[i] = i + 1;
choices.insert(mp(-a[i], i));
}
ll ans = 0;
for (ll c = 0; c < (n + 1) / 2; c++){
pll mx = *choices.begin();
choices.erase(choices.begin());
ans -= mx.fi;
ll id = mx.se, lf = l[id], rg = r[id];
if (lf) choices.erase(mp(-a[lf], lf));
if (rg <= n) choices.erase(mp(-a[rg], rg));
if (lf) l[id] = l[lf];
else l[id] = 0;
if (rg <= n) r[id] = r[rg];
else r[id] = n + 1;
if (l[id]) r[l[id]] = id;
if (r[id] <= n) l[r[id]] = id;
a[id] = a[lf] + a[rg] - a[id];
choices.insert(mp(-a[id], id));
cout << ans << "\n";
}
}
Compilation message
candies.cpp:6: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
6 | #pragma GCC optimization ("unroll-loops, no-stack-protector")
|
candies.cpp:35: warning: ignoring #pragma 03 [-Wunknown-pragmas]
35 | #pragma 03
|
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
492 KB |
Output is correct |
| 2 |
Correct |
2 ms |
492 KB |
Output is correct |
| 3 |
Correct |
2 ms |
492 KB |
Output is correct |
| 4 |
Correct |
2 ms |
492 KB |
Output is correct |
| 5 |
Correct |
2 ms |
492 KB |
Output is correct |
| 6 |
Correct |
2 ms |
492 KB |
Output is correct |
| 7 |
Correct |
2 ms |
492 KB |
Output is correct |
| 8 |
Correct |
2 ms |
492 KB |
Output is correct |
| 9 |
Correct |
2 ms |
492 KB |
Output is correct |
| 10 |
Correct |
2 ms |
492 KB |
Output is correct |
| 11 |
Correct |
2 ms |
492 KB |
Output is correct |
| 12 |
Correct |
2 ms |
492 KB |
Output is correct |
| 13 |
Correct |
2 ms |
492 KB |
Output is correct |
| 14 |
Correct |
2 ms |
492 KB |
Output is correct |
| 15 |
Correct |
2 ms |
492 KB |
Output is correct |
| 16 |
Correct |
2 ms |
492 KB |
Output is correct |
| 17 |
Correct |
2 ms |
492 KB |
Output is correct |
| 18 |
Correct |
3 ms |
492 KB |
Output is correct |
| 19 |
Correct |
2 ms |
492 KB |
Output is correct |
| 20 |
Correct |
2 ms |
492 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
492 KB |
Output is correct |
| 2 |
Correct |
2 ms |
492 KB |
Output is correct |
| 3 |
Correct |
2 ms |
492 KB |
Output is correct |
| 4 |
Correct |
2 ms |
492 KB |
Output is correct |
| 5 |
Correct |
2 ms |
492 KB |
Output is correct |
| 6 |
Correct |
2 ms |
492 KB |
Output is correct |
| 7 |
Correct |
2 ms |
492 KB |
Output is correct |
| 8 |
Correct |
2 ms |
492 KB |
Output is correct |
| 9 |
Correct |
2 ms |
492 KB |
Output is correct |
| 10 |
Correct |
2 ms |
492 KB |
Output is correct |
| 11 |
Correct |
2 ms |
492 KB |
Output is correct |
| 12 |
Correct |
2 ms |
492 KB |
Output is correct |
| 13 |
Correct |
2 ms |
492 KB |
Output is correct |
| 14 |
Correct |
2 ms |
492 KB |
Output is correct |
| 15 |
Correct |
2 ms |
492 KB |
Output is correct |
| 16 |
Correct |
2 ms |
492 KB |
Output is correct |
| 17 |
Correct |
2 ms |
492 KB |
Output is correct |
| 18 |
Correct |
3 ms |
492 KB |
Output is correct |
| 19 |
Correct |
2 ms |
492 KB |
Output is correct |
| 20 |
Correct |
2 ms |
492 KB |
Output is correct |
| 21 |
Correct |
424 ms |
19180 KB |
Output is correct |
| 22 |
Correct |
439 ms |
19180 KB |
Output is correct |
| 23 |
Correct |
397 ms |
19240 KB |
Output is correct |
| 24 |
Correct |
150 ms |
19052 KB |
Output is correct |
| 25 |
Correct |
155 ms |
19052 KB |
Output is correct |
| 26 |
Correct |
159 ms |
19052 KB |
Output is correct |
| 27 |
Correct |
165 ms |
19052 KB |
Output is correct |
| 28 |
Correct |
164 ms |
19052 KB |
Output is correct |
| 29 |
Correct |
170 ms |
19180 KB |
Output is correct |
| 30 |
Correct |
175 ms |
19180 KB |
Output is correct |
| 31 |
Correct |
176 ms |
19180 KB |
Output is correct |
| 32 |
Correct |
200 ms |
19076 KB |
Output is correct |
| 33 |
Correct |
269 ms |
19052 KB |
Output is correct |
| 34 |
Correct |
294 ms |
19052 KB |
Output is correct |
| 35 |
Correct |
277 ms |
19216 KB |
Output is correct |
| 36 |
Correct |
430 ms |
19308 KB |
Output is correct |
| 37 |
Correct |
408 ms |
19136 KB |
Output is correct |
| 38 |
Correct |
444 ms |
19180 KB |
Output is correct |
| 39 |
Correct |
152 ms |
19052 KB |
Output is correct |
| 40 |
Correct |
185 ms |
19180 KB |
Output is correct |
| 41 |
Correct |
162 ms |
19052 KB |
Output is correct |
| 42 |
Correct |
165 ms |
19052 KB |
Output is correct |
| 43 |
Correct |
165 ms |
19100 KB |
Output is correct |
| 44 |
Correct |
186 ms |
19072 KB |
Output is correct |
| 45 |
Correct |
180 ms |
19180 KB |
Output is correct |
| 46 |
Correct |
204 ms |
19052 KB |
Output is correct |
| 47 |
Correct |
183 ms |
19052 KB |
Output is correct |
| 48 |
Correct |
273 ms |
19052 KB |
Output is correct |
| 49 |
Correct |
287 ms |
19180 KB |
Output is correct |
| 50 |
Correct |
284 ms |
19180 KB |
Output is correct |
