#include <iostream>
#include <vector>
#include <algorithm>
typedef long long ll;
using namespace std;
void upd(ll& a, const ll& b) { a = max(a, b); }
ll findMaxAttraction(int n, int s, int d, int a[])
{
const ll minf = -1e18;
vector<vector<ll> > dp(3, vector<ll>(n, minf));
// ked sme v meste i tak predpokladame ze sme sa uz rozhodli ze ci sme ho navstivili
dp[0][s] = 0; // az potom sa rozhodneme ci navstivime tuto atrakciu
ll ans = minf;
vector<ll> lf(d + n + 1, 0), ri(d + n + 1, 0), lf0(d + 1, 0), ri0(d + 1, 0);
for (int t = 0; t <= d; t++)
{
for (int i = 0; i < n; i++)
{
upd(dp[1][i], dp[0][i]);
if (i <= s && i)
{
upd(dp[1][i - 1], dp[0][i]);
upd(dp[2][i - 1], dp[0][i] + a[i - 1]);
}
if (i >= s && i + 1 < n)
{
upd(dp[1][i + 1], dp[0][i]);
upd(dp[2][i + 1], dp[0][i] + a[i + 1]);
}
if (i < s)
upd(lf[t + abs(i - s)], dp[0][i]), upd(lf0[t], dp[0][i]);
if (i > s)
upd(ri[t + abs(i - s)], dp[0][i]), upd(ri0[t], dp[0][i]);
upd(ans, dp[0][i]);
}
dp[0] = dp[1]; dp[1] = dp[2];
for (int i = 0; i < n; i++) dp[2][i] = minf;
}
for (int vis = 0; vis < 2; vis++) for (int t = 0; t + vis <= d; t++)
{
upd(ans, lf0[t] + ri[d - t - vis] + vis * a[s]);
upd(ans, ri0[t] + lf[d - t - vis] + vis * a[s]);
}
return ans;
}
