#include <bits/stdc++.h>
using namespace std;
const int N = 200005;
struct segment {
int l; int r;
long long real; long long hidden;
segment(int l=0, int r=0, long long real=0, long long hidden=0):
l(l), r(r), real(real), hidden(hidden) {}
bool operator < (const segment &other) const {
return l < other.l || (l == other.l && r < other.r);
}
};
set <segment> s;
set < pair<long long, pair<int,int> > > pq;
int n, a[N];
long long res;
int main() {
ios_base::sync_with_stdio(false); cin.tie(0);
cin >> n;
s.insert(segment(0, 0, 0, 0));
s.insert(segment(n + 1, n + 1, 0, 0));
for (int i = 1; i <= n; ++i) {
cin >> a[i];
s.insert(segment(i, i, 0, a[i]));
pq.insert(make_pair(a[i], make_pair(i, i)));
}
for (int have = 1; have <= (n + 1) / 2; ++have) {
auto top = (*pq.rbegin()); pq.erase(--pq.end());
res += top.first;
// update the current segment
set <segment>::iterator it = s.lower_bound(segment(top.second.first, top.second.second));
auto cur = (*it);
swap(cur.real, cur.hidden);
set <segment>::iterator prv, nxt;
if (it != s.begin()) {
prv = prev(it);
cur.real += (prv -> real); cur.hidden += (prv -> hidden); cur.l = (prv -> l);
pq.erase(make_pair(prv -> hidden - prv -> real, make_pair(prv -> l, prv -> r)));
}
if (it != --s.end()) {
nxt = next(it);
cur.real += (nxt ->real); cur.hidden += (nxt -> hidden); cur.r = (nxt -> r);
pq.erase(make_pair(nxt -> hidden - nxt -> real, make_pair(nxt -> l, nxt -> r)));
}
if (it != s.begin()) s.erase(prv);
if (it != --s.end()) s.erase(nxt);
s.erase(it);
s.insert(cur);
if (cur.l != 0 && cur.r != n + 1) {
// we cannot increase the number of chosen cells with this type of segment
pq.insert(make_pair(cur.hidden - cur.real, make_pair(cur.l, cur.r)));
}
printf("%lld\n", res);
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
632 KB |
Output is correct |
| 2 |
Correct |
4 ms |
712 KB |
Output is correct |
| 3 |
Correct |
6 ms |
720 KB |
Output is correct |
| 4 |
Correct |
4 ms |
820 KB |
Output is correct |
| 5 |
Correct |
4 ms |
964 KB |
Output is correct |
| 6 |
Correct |
4 ms |
964 KB |
Output is correct |
| 7 |
Correct |
4 ms |
968 KB |
Output is correct |
| 8 |
Correct |
4 ms |
1036 KB |
Output is correct |
| 9 |
Correct |
4 ms |
1064 KB |
Output is correct |
| 10 |
Correct |
4 ms |
1228 KB |
Output is correct |
| 11 |
Correct |
4 ms |
1228 KB |
Output is correct |
| 12 |
Correct |
4 ms |
1228 KB |
Output is correct |
| 13 |
Correct |
4 ms |
1228 KB |
Output is correct |
| 14 |
Correct |
4 ms |
1228 KB |
Output is correct |
| 15 |
Correct |
5 ms |
1228 KB |
Output is correct |
| 16 |
Correct |
4 ms |
1236 KB |
Output is correct |
| 17 |
Correct |
4 ms |
1260 KB |
Output is correct |
| 18 |
Correct |
5 ms |
1260 KB |
Output is correct |
| 19 |
Correct |
4 ms |
1296 KB |
Output is correct |
| 20 |
Correct |
4 ms |
1316 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
632 KB |
Output is correct |
| 2 |
Correct |
4 ms |
712 KB |
Output is correct |
| 3 |
Correct |
6 ms |
720 KB |
Output is correct |
| 4 |
Correct |
4 ms |
820 KB |
Output is correct |
| 5 |
Correct |
4 ms |
964 KB |
Output is correct |
| 6 |
Correct |
4 ms |
964 KB |
Output is correct |
| 7 |
Correct |
4 ms |
968 KB |
Output is correct |
| 8 |
Correct |
4 ms |
1036 KB |
Output is correct |
| 9 |
Correct |
4 ms |
1064 KB |
Output is correct |
| 10 |
Correct |
4 ms |
1228 KB |
Output is correct |
| 11 |
Correct |
4 ms |
1228 KB |
Output is correct |
| 12 |
Correct |
4 ms |
1228 KB |
Output is correct |
| 13 |
Correct |
4 ms |
1228 KB |
Output is correct |
| 14 |
Correct |
4 ms |
1228 KB |
Output is correct |
| 15 |
Correct |
5 ms |
1228 KB |
Output is correct |
| 16 |
Correct |
4 ms |
1236 KB |
Output is correct |
| 17 |
Correct |
4 ms |
1260 KB |
Output is correct |
| 18 |
Correct |
5 ms |
1260 KB |
Output is correct |
| 19 |
Correct |
4 ms |
1296 KB |
Output is correct |
| 20 |
Correct |
4 ms |
1316 KB |
Output is correct |
| 21 |
Correct |
682 ms |
30300 KB |
Output is correct |
| 22 |
Correct |
672 ms |
32152 KB |
Output is correct |
| 23 |
Correct |
665 ms |
33328 KB |
Output is correct |
| 24 |
Correct |
326 ms |
33328 KB |
Output is correct |
| 25 |
Correct |
330 ms |
33328 KB |
Output is correct |
| 26 |
Correct |
333 ms |
33328 KB |
Output is correct |
| 27 |
Correct |
333 ms |
33376 KB |
Output is correct |
| 28 |
Correct |
335 ms |
33376 KB |
Output is correct |
| 29 |
Correct |
334 ms |
33376 KB |
Output is correct |
| 30 |
Correct |
353 ms |
33376 KB |
Output is correct |
| 31 |
Correct |
350 ms |
33376 KB |
Output is correct |
| 32 |
Correct |
376 ms |
33376 KB |
Output is correct |
| 33 |
Correct |
509 ms |
33376 KB |
Output is correct |
| 34 |
Correct |
498 ms |
33376 KB |
Output is correct |
| 35 |
Correct |
491 ms |
33400 KB |
Output is correct |
| 36 |
Correct |
701 ms |
33400 KB |
Output is correct |
| 37 |
Correct |
740 ms |
33400 KB |
Output is correct |
| 38 |
Correct |
747 ms |
33400 KB |
Output is correct |
| 39 |
Correct |
334 ms |
33400 KB |
Output is correct |
| 40 |
Correct |
314 ms |
33400 KB |
Output is correct |
| 41 |
Correct |
321 ms |
33400 KB |
Output is correct |
| 42 |
Correct |
331 ms |
33400 KB |
Output is correct |
| 43 |
Correct |
336 ms |
33400 KB |
Output is correct |
| 44 |
Correct |
349 ms |
33400 KB |
Output is correct |
| 45 |
Correct |
354 ms |
33400 KB |
Output is correct |
| 46 |
Correct |
357 ms |
33400 KB |
Output is correct |
| 47 |
Correct |
355 ms |
33400 KB |
Output is correct |
| 48 |
Correct |
492 ms |
33400 KB |
Output is correct |
| 49 |
Correct |
496 ms |
33400 KB |
Output is correct |
| 50 |
Correct |
496 ms |
33460 KB |
Output is correct |
