#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
ll sub1(int n, int start, int d, int attraction[]) {
ll toRet = 0;
for (int i = 0; i <= start; i++)
{
for (int j = start; j < n; j++)
{
int daysTravel = min(2*(j-start) + (start-i), 2*(start-i) + (j-start));
if (daysTravel >= d)
{
continue;
}
vector<int> v;
for (int k = i; k <= j; k++)
{
v.push_back(attraction[k]);
}
sort(v.rbegin(), v.rend());
ll thisToRet = 0;
for (int k = 0; k < min(d-daysTravel, int(v.size()) ); k++)
{
thisToRet += v[k];
}
toRet = max(toRet, thisToRet);
}
}
return toRet;
}
ll findMaxAttraction(int n, int start, int d, int attraction[]) {
if (n <= 20)
{
return sub1(n, start, d, attraction);
}
ll finAns = 0;
ll totSum = 0;
ll toKickOut = 1000000009;
priority_queue<ll> s;
for (int i = 0; i < min(n, (d+1)/2); i++)
{
s.push(-attraction[i]);
totSum += attraction[i];
toKickOut = min(toKickOut, ll(attraction[i]));
}
finAns = max(finAns, totSum);
int parity = (d+1)%2;
int pointer = min(n, (d+1)/2);
//cout << "Start with " << totSum << "\n";
while (!s.empty() and pointer < n)
{
//cout << "Pointer is " << pointer << " and parity is " << parity << "\n";
if (parity == 0)
{
totSum += s.top();
//cout << "Removing " << -s.top() << " new sum is " << totSum << "\n";
s.pop();
}
if (attraction[pointer] > -s.top())
{
totSum += attraction[pointer];
totSum += s.top();
//cout << "Swapping out " << -s.top() << " for " << attraction[pointer] << " new sum is " << totSum << "\n";
s.pop();
s.push(-attraction[pointer]);
finAns = max(finAns, totSum);
}
parity = 1-parity;
pointer++;
}
return finAns;
}
