#include <bits/stdc++.h>
#define f first
#define s second
#define sz(x) (int)x.size()
#define rep(i, l, r) for (int i = (l); i <= (r); i++)
#define per(i, l, r) for (int i = (l); i >= (r); i--)
#define nl '\n'
#define ioi exit(0);
using namespace std;
typedef long long ll;
const int N = (int)2e5 + 7;
int n;
int a[N];
ll c[N];
int L[N], R[N];
int main() {
ios_base :: sync_with_stdio(0);
cin.tie(0), cout.tie(0);
#ifdef IOI
freopen ("in.txt", "r", stdin);
freopen ("A.out", "w", stdout);
#endif
cin >> n;
multiset < pair <ll, int> > st;
rep(i, 1, n) {
cin >> a[i];
st.insert({a[i], i});
c[i] = a[i];
L[i] = R[i] = i;
}
ll sum = 0;
rep(j, 1, (n + 1) / 2) {
ll ans = st.rbegin() -> f;
int p = st.rbegin() -> s;
st.erase(--st.end());
ll x = -ans;
int l = p, r = R[p];
int f = 0;
if (p > 1) {
x += c[L[p - 1]];
f++;
l = L[p - 1];
st.erase({c[L[p - 1]], L[p - 1]});
}
if (R[p] < n) {
x += c[R[p] + 1];
f++;
r = R[R[p] + 1];
st.erase({c[R[p] + 1], R[p] + 1});
}
L[r] = l;
R[l] = r;
c[l] = x;
if (f == 2) st.insert({x, l});
/*cerr << ans << ' ' << x << " -> \n";
for (auto it : st) cerr << it.f << ' ' << it.s << nl;
cerr << nl;*/
// cout << ans << nl;
sum += ans;
cout << sum << nl;
}
ioi
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
3 ms |
504 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
3 ms |
504 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
