#include"holiday.h"
#include <cstdio>
#include <cassert>
#include <vector>
#include <set>
#include <algorithm>
template<typename T> bool ckmax(T& a, const T& b) {return b>a?a=b,1:0;}
template<typename T> bool ckmin(T& a, const T& b) {return b<a?a=b,1:0;}
using ll = long long;
int D;
std::vector<int> a;
struct tbd
{
public:
int u, v, l, r;
};
struct bset
{
public:
std::multiset<int> active, bench;
ll val;
int u;
bset(): val(0), u(D+1), active(), bench() {}
void incu()
{
if(0 <= u && !bench.empty())
val += *bench.rbegin(), active.insert(*bench.rbegin()), bench.erase(std::prev(bench.end()));
++u;
}
void decu()
{
if(0 < u && u <= active.size())
val -= *active.begin(), bench.insert(*active.begin()), active.erase(active.begin());
--u;
}
void ins(int v)
{
val += v;
active.insert(v);
if(active.size() > u)
{
val -= *active.begin();
bench.insert(*active.begin());
active.erase(active.begin());
}
decu();
}
void rem(int v)
{
if(bench.find(v) != bench.end())
bench.erase(bench.find(v));
else
{
auto it=active.find(v);
assert(it != active.end());
val -= *it;
active.erase(it);
if(!bench.empty())
val += *bench.rbegin(), active.insert(*bench.rbegin()), bench.erase(std::prev(bench.end()));
}
incu();
}
};
ll getans(int start) // x is central
{
std::vector<tbd> todo, next;
std::vector<ll> ans(start+1, -1);
todo.push_back({0, start+1, start+1, a.size()});
for(;!todo.empty();)
{
bset set;
int bl = start+1, br = start+1;
for(;bl>0;)
set.ins(a[--bl]);
for(auto x: todo)
{
int u=x.u, v=x.v, l=x.l, r=x.r;
int w = (u+v)/2;
for(;br < l;)
set.ins(a[br++]);
for(;bl < w;)
set.rem(a[bl++]);
int m = l;
ll bv = set.val;
for(;br < r;)
{
set.ins(a[br++]);
if(ckmax(bv, set.val))
m=br;
}
ans[w] = bv;
if(u<w) next.push_back({u, w, l, m});
if(w+1<v) next.push_back({w+1, v, m, r});
}
todo.clear();
todo.swap(next);
}
return *std::max_element(ans.begin(), ans.end());
}
ll findMaxAttraction(int n, int start, int d, int attraction[])
{
D = d;
ll ans=0;
{ // double left
a.clear();
for(int i=0;i<n;++i)
{
a.push_back(attraction[i]);
if(i < start)
a.push_back(0);
}
ckmax(ans, getans(start*2));
}
{ // double right
a.clear();
for(int i=0;i<n;++i)
{
a.push_back(attraction[i]);
if(i >= start)
a.push_back(0);
}
ckmax(ans, getans(start));
}
return ans;
}
