#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int mxN = 2e5 + 5, mod = 1e9 + 7, LOG = 20;
int n;
pair <int, int> cons[mxN];
ll a[mxN];
int main() {
ios :: sync_with_stdio(false), cin.tie(nullptr);
cin >> n;
set <pair <ll, int> > st;
for (int i = 1; i <= n; ++i) {
cin >> a[i];
cons[i] = {i - 1, i + 1};
st.insert({a[i], i});
}
ll ans = 0;
for (int i = 1; i <= (n + 1) / 2; ++i) {
cout << '\n';
auto x = *(--st.end());
ans += x.first;
st.erase(x);
int lb = cons[x.second].first, rb = cons[x.second].second;
if (lb) st.erase({a[lb], lb});
if (rb <= n) st.erase({a[rb], rb});
if (lb && rb <= n) {
a[x.second] = a[lb] + a[rb] - a[x.second];
st.insert({a[x.second], x.second});
cons[x.second] = {cons[lb].first, cons[rb].second};
cons[cons[lb].first].second = x.second;
cons[cons[rb].second].first = x.second;
}
else {
swap(cons[cons[rb].second].first, cons[cons[lb].first].second);
}
cout << ans << '\n';
}
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
460 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
460 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
