#include <bits/stdc++.h>
#define int long long
template <class A, class B>
bool maximize (A &a, const B b){
if (a < b) {
a = b;
return true;
} return false;
}
template <class A, class B>
bool minimize (A &a, const B b) {
if (a > b) {
a = b;
return true;
} return false;
}
#define FOR(i, a, b) for(int i = (a); i <= (int)(b); i++)
#define FORD(i, a, b) for(int i = (a); i >= (int)(b); i--)
#define fi first
#define se second
#define pb push_back
#define ALL(A) A.begin(), A.end()
#define BIT(mask,i) ((mask>>(i))&1)
#define ll long long
using namespace std;
const int maxN = 2e5 + 5;
int n;
int a[maxN], L[maxN], R[maxN];
void init(void) {
cin >> n;
FOR(i, 1, n) cin >> a[i];
}
void process(void) {
a[0] = a[n + 1] = - maxN;
priority_queue <pair <int, int>, vector <pair <int, int>>> PQ;
FOR(i, 1, n) {
L[i] = i - 1;
R[i] = i + 1;
PQ.push({a[i], i});
}
vector <int> dd(n + 5, 0);
long long ans = 0;
FOR(id, 1, (n + 1) / 2) {
while (!PQ.empty() && dd[PQ.top().second]) PQ.pop();
auto [val, i] = PQ.top(); PQ.pop();
dd[L[i]] = dd[R[i]] = 1;
ans+= val;
a[i] = a[L[i]] + a[R[i]] - a[i];
PQ.push({a[i], i});
L[i] = L[L[i]];
R[L[i]] = i;
R[i] = R[R[i]];
L[R[i]] = i;
cout << ans << "\n";
}
}
signed main(void) {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define koa "candies"
if (fopen(koa".inp", "r")) {
freopen(koa".inp", "r", stdin);
freopen(koa".out", "w", stdout);
}
init();
process();
return 0;
}
Compilation message (stderr)
candies.cpp: In function 'int main()':
candies.cpp:69:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
69 | freopen(koa".inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
candies.cpp:70:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
70 | freopen(koa".out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |