#include "holiday.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int INF = numeric_limits<int>::max() / 2;
void dodp(int n, int d, int attraction[], int step, int cost, vector<int>& out) {
vector<int> dp(d+1,0);
int *pos = attraction;
for (int i{0};i<n;++i) {
vector<int> ndp(d+1,0);
ndp[0] = -INF;
if (cost == 1) {
if (d>=1) {
ndp[1] = dp[0];
if (d>=2) {
ndp[2] = max(dp[2-cost-1]+*pos,dp[2-cost]);
out[2] = max(ndp[2],out[2]);
}
}
}
if (cost == 2) {
if (d>=1) {
ndp[1] = -INF;
if (d>=2) {
ndp[2] = dp[0];
}}
}
for (int j{3};j<d+1;++j) {
ndp[j] = max(dp[j-cost-1]+*pos,dp[j-cost]);
out[j] = max(ndp[j],out[j]);
}
ndp.swap(dp);
pos += step;
}
}
long long int findMaxAttraction(int n, int start, int d, int attraction[])
{
if (start == 0)
{
ll out = 0;
ll cur = 0;
ll get = d + 1;
ll size = 0;
ll i = 0;
priority_queue<int, std::vector<int>, std::greater<int>> pq{};
while (get > size + 1 && i < n)
{
pq.push(attraction[i]);
cur += attraction[i];
--get;
++size;
++i;
}
if (get > size && i < n)
{
pq.push(attraction[i]);
cur += attraction[i];
cur -= pq.top();
pq.pop();
--get;
++i;
}
out = cur;
while (i < n)
{
pq.push(attraction[i]);
cur += attraction[i];
cur -= pq.top();
pq.pop();
if (pq.empty())
{
break;
}
cur -= pq.top();
pq.pop();
out = max(out, cur);
--get;
--size;
++i;
}
return out;
}
int l1 = start;
int l2 = n-start-1;
int *seg1 = attraction;
int *seg2 = attraction+start+1;
vector<int> dpl1(d+1,0);
dodp(l1,d,seg1,-1,1,dpl1);
vector<int> dpl2(d+1,0);
dodp(l1,d,seg1,-1,2,dpl2);
vector<int> dpr1(d+1,0);
dodp(l2,d,seg2,1,1,dpr1);
vector<int> dpr2(d+1,0);
dodp(l2,d,seg2,1,2,dpr2);
int out = 0;
out = max(out,dpl1[0]+dpr2[d]);
out = max(out,dpl2[0]+dpr1[d]);
for (int i{1};i<d+1;++i){
out = max(out,dpl1[i]+dpr2[d-i]);
out = max(out,dpl2[i]+dpr1[d-i]);
out = max(out,dpl1[i-1]+dpr2[d-i]+attraction[start]);
out = max(out,dpl2[i-1]+dpr1[d-i]+attraction[start]);
}
return out;
}
