#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 oneCase(int n, int d, priority_queue<ll> s, int start, int attraction[], ll startSum) {
ll totSum = startSum;
ll finAns = 0;
while (s.size() > d)
{
totSum += s.top();
s.pop();
}
int freeDays = d - s.size();
for (int i = start; i < min(n, (freeDays+1)/2 + start); i++)
{
s.push(-attraction[i]);
totSum += attraction[i];
}
finAns = max(finAns, totSum);
// cout << "We have " << finAns << " in the queue and " << d << " days\n";
int pointer = min(n, (freeDays+1)/2 + start);
while (!s.empty() and pointer < n)
{
if (attraction[pointer] > -s.top())
{
totSum += attraction[pointer];
totSum += s.top();
s.pop();
s.push(-attraction[pointer]);
}
int numFree = start + d - pointer;
while (numFree < s.size())
{
totSum += s.top();
s.pop();
}
finAns = max(finAns, totSum);
pointer++;
}
return finAns;
}
ll twoCase(int n, int d, priority_queue<ll> s, int start, int attraction[], ll startSum) {
ll totSum = startSum;
ll finAns = 0;
while (s.size() > d)
{
totSum += s.top();
s.pop();
}
int freeDays = d - s.size();
for (int i = start; i > max(-1, start - (freeDays+1)/2); i--)
{
s.push(-attraction[i]);
totSum += attraction[i];
}
finAns = max(finAns, totSum);
// cout << "We have " << finAns << " in the queue and " << d << " days\n";
int pointer = max(-1, start - (freeDays+1)/2);
while (!s.empty() and pointer >= 0)
{
if (attraction[pointer] > -s.top())
{
totSum += attraction[pointer];
totSum += s.top();
s.pop();
s.push(-attraction[pointer]);
}
int numFree = d - (start - pointer);
while (numFree < s.size())
{
totSum += s.top();
s.pop();
}
finAns = max(finAns, totSum);
pointer--;
}
return finAns;
}
ll sub3(int n, int start, int d, int attraction[]) {
ll finAns = 0;
ll totSum = 0;
priority_queue<ll> s;
for (int i = start; i < min(n, (d+1)/2 + start); i++)
{
s.push(-attraction[i]);
totSum += attraction[i];
}
finAns = max(finAns, totSum);
int pointer = min(n, (d+1)/2 + start);
while (!s.empty() and pointer < n)
{
if (attraction[pointer] > -s.top())
{
totSum += attraction[pointer];
totSum += s.top();
s.pop();
s.push(-attraction[pointer]);
}
int numFree = start + d - pointer;
while (numFree < s.size())
{
totSum += s.top();
s.pop();
}
finAns = max(finAns, totSum);
pointer++;
}
while (!s.empty())
{
s.pop();
}
//cout << "Going right we have " << finAns << "\n";
totSum = 0;
for (int i = start; i > max(-1, start - (d+1)/2); i--)
{
s.push(-attraction[i]);
totSum += attraction[i];
}
finAns = max(finAns, totSum);
pointer = max(-1, start - (d+1)/2);
while (!s.empty() and pointer >= 0)
{
if (attraction[pointer] > -s.top())
{
totSum += attraction[pointer];
totSum += s.top();
s.pop();
s.push(-attraction[pointer]);
}
int numFree = d - (start - pointer);
while (numFree < s.size())
{
totSum += s.top();
s.pop();
}
finAns = max(finAns, totSum);
pointer--;
}
while (!s.empty())
{
s.pop();
}
//cout << "Going left we have " << finAns << "\n";
ll startSum = 0;
for (int i = start-1; i >= 0; i--)
{
startSum += attraction[i];
s.push(-attraction[i]);
if (2 * (start-i) < d)
{
//cout << "Going from " << i << " we have " << oneCase(n, d - 2*(start-i), s, start, attraction, startSum) << "\n";
finAns = max(finAns, oneCase(n, d - 2*(start-i), s, start, attraction, startSum));
}
}
while (!s.empty())
{
s.pop();
}
startSum = 0;
for (int i = start+1; i < n; i++)
{
//cout << "i = " << i << "\n";
startSum += attraction[i];
s.push(-attraction[i]);
if (2 * (i-start) < d)
{
//cout << "Going from " << i << " we have " << twoCase(n, d - 2*(i-start), s, start, attraction, startSum) << "\n";
finAns = max(finAns, twoCase(n, d - 2*(i-start), s, start, attraction, startSum));
}
}
return finAns;
}
ll findMaxAttraction(int n, int start, int d, int attraction[]) {
if (n <= 3000)
{
return sub3(n, start, d, 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 pointer = min(n, (d+1)/2);
while (!s.empty() and pointer < n)
{
if (attraction[pointer] > -s.top())
{
totSum += attraction[pointer];
totSum += s.top();
s.pop();
s.push(-attraction[pointer]);
}
int numFree = d - pointer;
while (numFree < s.size())
{
totSum += s.top();
s.pop();
}
finAns = max(finAns, totSum);
pointer++;
}
return finAns;
}
