#include <bits/stdc++.h>
using namespace std;
#define finish(x) return cout << x << endl, 0
#define ll long long
int n;
vector <int> a;
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n;
a.resize(n);
for(auto &i : a) cin >> i;
set <int> alive;
set <pair <ll, int> > s;
for(int i = 0 ; i < n ; i++){
alive.insert(i);
s.insert(make_pair(a[i], i));
}
ll ans = 0;
for(int itt = 0 ; itt < (n + 1) / 2 ; itt++){
auto top = *--s.end();
s.erase(--s.end());
ans += top.first;
cout << ans << endl;
int pos = top.second;
alive.erase(pos);
a[pos] *= -1;
auto it = alive.upper_bound(pos);
if(it != alive.end()){
a[pos] += a[*it];
s.erase(make_pair(a[*it], *it));
alive.erase(*it);
}
it = alive.upper_bound(pos);
if(it != alive.begin()){
it--;
a[pos] += a[*it];
s.erase(make_pair(a[*it], *it));
alive.erase(*it);
}
alive.insert(pos);
s.insert(make_pair(a[pos], pos));
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
844 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
844 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
