#include <bits/stdc++.h>
#define mk make_pair
#define sc second
#define fr first
#define pb emplace_back
#define all(s) s.begin(), s.end()
#define sz(s) ( (int)s.size() )
#define Scan(a) scanf ("%I64d", &a)
#define scan(a) scanf ("%d", &a)
#define int long long
using namespace std;
const int inf = (int)1e9 + 7;
const int N = (int)2e5 + 7;
int n;
int a[N];
int od,ev;
int res;
int nxt[N],lst[N];
int prs[N],pr[N];
int ll,rr,mx;
int f[N];
vector <int> ans;
struct node {
int mx,cur,nxt,prv,id;
node() {
mx = cur = nxt = prv = id = 0;
}
}t[N * 4];
node tt[20][N];
node merge(node a,node b) {
if (a.mx >= b.mx)
return a;
return b;
}
void buildtable() {
for (int i = 0; i <= ceil(log2(n)); i ++) {
for (int j = 1; j <= n; j ++) {
if (i == 0) {
tt[i][j].mx = a[j];
tt[i][j].id = j;
continue;
}
tt[i][j] = merge(tt[i - 1][j],tt[i - 1][j + (1 << (i - 1))]);
}
}
}
node getmax(int l,int r) {
node cp;
if (l > r || l == 0 || r == n + 1)
return cp;
int cur = log2(r - l + 1);
return merge(tt[cur][l],tt[cur][r - (1 << cur) + 1]);
}
void build (int v = 1,int tl = 1,int tr = n) {
if (tl == tr) {
if (f[tl]) {
int ps = 0;
for (ps = tl - 1; ps >= 0; ps --)
if (f[ps])
break;
t[v].prv = ps;
lst[tl] = t[v].prv;
for (ps = tl + 1; ps <= n + 1; ps ++)
if (f[ps])
break;
t[v].nxt = ps;
nxt[tl] = t[v].nxt;
t[v].id = tl;
t[v].mx = (getmax(t[v].prv,tl - 1).mx + getmax(tl + 1,t[v].nxt).mx) - (a[tl] + a[t[v].prv] + a[t[v].nxt]);
}
else t[v].mx = -inf;
}
else {
int tm = (tl + tr) >> 1;
build(v + v,tl,tm);
build(v + v + 1,tm + 1,tr);
t[v] = merge(t[v + v],t[v + v + 1]);
}
}
void update (int pos,int v = 1,int tl = 1,int tr = n) {
if (tl == tr)
t[v].mx = -inf;
else {
int tm = (tl + tr) >> 1;
if (pos <= tm)
update (pos,v + v,tl,tm);
else
update (pos,v + v + 1,tm + 1,tr);
t[v] = merge(t[v + v],t[v + v + 1]);
}
}
void Update (int pos,int l,int r,int v = 1,int tl = 1,int tr = n) {
if (tl == tr) {
t[v].prv = l;
lst[tl] = t[v].prv;
t[v].nxt = r;
nxt[tl] = t[v].nxt;
t[v].id = tl;
t[v].mx = (getmax(t[v].prv,tl - 1).mx + getmax(tl + 1,t[v].nxt).mx) - (a[tl] + a[t[v].prv] + a[t[v].nxt]);
}
else {
int tm = (tl + tr) >> 1;
if (pos <= tm)
Update (pos,l,r,v + v,tl,tm);
else
Update (pos,l,r,v + v + 1,tm + 1,tr);
t[v] = merge(t[v + v],t[v + v + 1]);
}
}
main () {
cin >> n;
for (int i = 1; i <= n; i ++) {
cin >> a[i];
pr[i] = pr[max(0ll,i - 2)] + a[i];
if (i % 2) od += a[i];
else ev += a[i];
}
prs[n + 1] = 0;
for (int i = n; i >= 1; i --) {
prs[i] = prs[min(n + 1,i + 2)] + a[i];
}
buildtable();
a[n + 1] = 0;
for (int i = 1; i <= n - 1; i ++) {
if (mx < pr[i - 1] + prs[i + 2])
mx = pr[i - 1] + prs[i + 2],ll = i,rr = i + 1;
}
if (mx <= od || mx <= ev) {
if (od > ev || n & 1){
res = od;
for (int i = 1; i <= n; i ++)
if (i % 2 == 0)
f[i] = 1;
}
else {
for (int i = 1; i <= n; i ++)
if (i % 2 == 0)
f[i] = 1;
res = ev;
}
build();
}
else{
res = mx;
for (int i = 1; i < ll; i ++)
if (i % 2 != ll % 2)
f[i] = 1;
for (int i = rr + 1; i <= n; i ++)
if (i % 2 != rr % 2)
f[i] = 1;
build();
}
ans.pb(res);
lst[0] = 0;
nxt[n + 1] = n + 1;
for (int i = (n + 1) / 2 - 1; i >= 1; i --) {
node c = t[1];
res += c.mx;
ans.pb(res);
int aa = lst[c.prv];
int bb = c.id;
int cc = nxt[c.nxt];
node f = getmax(c.prv,bb - 1);
node s = getmax(bb + 1,c.nxt);
//
update (c.id);
update (c.prv);
update (c.nxt);
if (f.id != 0)
Update (f.id,aa,s.id);
if (s.id != 0)
Update (s.id,f.id,cc);
}
reverse(ans.begin(),ans.end());
for (auto to : ans)
cout << to << endl;
}
Compilation message
candies.cpp:123:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
main () {
^
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
128 ms |
188280 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
128 ms |
188280 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
