#include"holiday.h"
#include<bits/stdc++.h>
using namespace std;
priority_queue<long long int> caso2;
pair<long long int,int> tabla_izq[250001],tabla_der[250001];
long long int tabla[3000][3000];
int valores[100000];
int ini=0;
int lim=0;
int lim_c;
void t_i(int dia,int i,long long int acum=0){
if(dia>lim||i<0) return;
long long int aux=acum+valores[i];
if(tabla_izq[dia].first<aux){
tabla_izq[dia].first=aux;
tabla_izq[dia].second=dia+ini-i;
}
t_i(dia+1,i-1,acum);
t_i(dia+2,i-1,acum+valores[i]);
}
void t_d(int dia,int i,long long int acum=0){
if(dia>lim||i>=lim_c) return;
long long int aux=acum+valores[i];
if(tabla_der[dia].first<aux){
tabla_der[dia].first=aux;
tabla_der[dia].second=dia+i-ini;
}
t_d(dia+1,i+1,acum);
t_d(dia+2,i+1,acum+valores[i]);
}
long long int findMaxAttraction(int n, int start, int d, int attraction[]) {
lim=d;
lim_c=n;
ini=start;
long long int res=0;
if(start==0){
long long int aux=0;
for(int i=0;i<n;i++){
if(d==0){
aux-=(caso2.top()*-1);
caso2.pop();
d++;
}
aux+=attraction[i];
res=max(res,aux);
caso2.push(attraction[i]*-1);
d--;
if(d==0){
aux-=(caso2.top()*-1);
caso2.pop();
}
else d--;
}
}
else{
for(int i=0;i<n;i++){
valores[i]=attraction[i];
}
t_i(2,start-1);
t_d(1,start);
for(int i=0;i<=d;i++){
res=max(res,tabla_der[i].first+tabla_izq[d-tabla_der[i].second].first);
}
for(int i=0;i<=d;i++){
res=max(res,tabla_izq[i].first+tabla_der[d-tabla_izq[i].second].first);
}
}
return res;
}
