#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct range{
int l, r;
ll on, off, delta;
range(){}
range(int &x, int &id){
l = r = id;
on = 0;
off = x;
delta = off - on;
}
void swp(){ swap(on, off); att(); }
void att(){ delta = off - on; }
bool operator<(const range &a) const { return delta < a.delta; }
};
int32_t main(){
ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
int n;
cin >> n;
vector<bool> is_corner(n+1), mark(n+1);
vector<range> v(n+1);
priority_queue<range> fila;
for(int i=1; i<=n; i++){
int x;
cin >> x;
fila.push(range(x, i));
v[i] = range(x, i);
}
int k = 0;
ll ans = 0;
while(k < ((n+1)>>1)){
range at = fila.top();
fila.pop();
//cout << at.l << " " << at.r << " " << fila.size() << endl;
if(at.l == at.r){ if(mark[at.l]) continue; }
else if(!(is_corner[at.l]&is_corner[at.r])) continue;
k++;
ans += at.delta;
at.swp();
if(at.l != 1){
if(is_corner[at.l-1]){
is_corner[at.l-1] = 0;
at.on += v[at.l-1].on, at.off += v[at.l-1].off;
at.l = v[at.l-1].l;
}
else{
at.off += v[--at.l].off;
mark[at.l] = 1;
}
}
if(at.r != n){
if(is_corner[at.r+1]){
is_corner[at.r+1] = 0;
at.on += v[at.r+1].on, at.off += v[at.r+1].off;
at.r = v[at.r+1].r;
}
else{
at.off += v[++at.r].off;
mark[at.r] = 1;
}
}
at.att();
v[at.l] = v[at.r] = at;
is_corner[at.l] = is_corner[at.r] = 1;
//cout << at.l << " " << at.r << " " << at.on << " " << at.off << " " << at.delta << endl;
cout << ans << "\n";
fila.push(at);
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
460 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
460 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
