#include"holiday.h"
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3")
int n, start, d;
vector<int> attraction;
vector<long long> F, S, F2, S2;
long long get(int l, int r, int k) {
long long res=0;
priority_queue<int> pq;
for(int i = l;i<=r;i++)pq.push(attraction[i]);
while(pq.size() && k>0) {
res+=pq.top();
pq.pop();
k--;
}
return res;
}
void calcf1(int l, int r, int pl, int pr) {
if(l>r)return;
int mid = (l+r)/2;
long long res=0;
int opt = pl;
for(int i = pl;i<=pr;i++) {
long long val = get(start, i, mid-abs(i-start));
if(val >= res) {
res=val;
opt=i;
}
}
F[mid] = res;
calcf1(l, mid-1, pl, opt);
calcf1(mid+1, r, opt, pr);
}
void calcs1(int l, int r, int pl, int pr) {
if(l>r)return;
int mid = (l+r)/2;
long long res=0;
int opt = pl;
for(int i = pl;i<=pr;i++) {
long long val = get(start, i, mid-2*abs(i-start));
if(val >= res) {
res=val;
opt=i;
}
}
S[mid] = res;
calcs1(l, mid-1, pl, opt);
calcs1(mid+1, r, opt, pr);
}
//
void calcf2(int l, int r, int pl, int pr) {
if(l>r)return;
int mid = (l+r)/2;
long long res=0;
int opt = pl;
for(int i = pl;i<=pr;i++) {
long long val = get(i, start-1, mid-abs(i-start));
if(val >= res) {
res=val;
opt=i;
}
}
F2[mid] = res;
calcf2(l, mid-1, opt, pr);
calcf2(mid+1, r, pl, opt);
}
void calcs2(int l, int r, int pl, int pr) {
if(l>r)return;
int mid = (l+r)/2;
long long res=0;
int opt = pl;
for(int i = pl;i<=pr;i++) {
long long val = get(i,start-1, mid-2*abs(i-start));
if(val >= res) {
res=val;
opt=i;
}
}
S2[mid] = res;
calcs2(l, mid-1, opt, pr);
calcs2(mid+1, r, pl, opt);
}
long long int findMaxAttraction(int _n, int _start, int _d, int _attraction[]) {
n=_n;
start=_start;
d=_d;
S.resize(d+1);
F.resize(d+1);
S2.resize(d+1);
F2.resize(d+1);
attraction=vector<int>(_attraction, _attraction+_n);
calcf1(1, _d, _start, _n-1);
calcs1(1, _d, _start, _n-1);
calcf2(1, _d, 0, _start-1);
calcs2(1, _d, 0, _start-1);
long long res=0;
for(int i = 0;i<=d;i++) {
res=max(res, F[i]+S2[d-i]);
res=max(res, S[i]+F2[d-i]);
}
return res;
}
