#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(d + 2, 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);
for (int t = 0; t < d; t++) for (int i = 0; i < n; i++)
{
upd(dp[t + 1][i], dp[t][i]);
if (i <= s && i)
{
upd(dp[t + 1][i - 1], dp[t][i]);
upd(dp[t + 2][i - 1], dp[t][i] + a[i - 1]);
}
if (i >= s && i + 1 < n)
{
upd(dp[t + 1][i + 1], dp[t][i]);
upd(dp[t + 2][i + 1], dp[t][i] + a[i + 1]);
}
}
for (int t = 0; t <= d; t++) for (int i = 0; i < n; i++)
{
//cout << dp[t][i] << " \n"[i == n - 1];
if (i < s)
upd(lf[t + abs(i - s)], dp[t][i]);
if (i > s)
upd(ri[t + abs(i - s)], dp[t][i]);
upd(ans, dp[t][i]);
}
for (int vis = 0; vis < 2; vis++) for (int t = 0; t + vis <= d; t++) for (int i = 0; i < n; i++)
{
if (i < s)
upd(ans, dp[t][i] + ri[d - t - vis] + vis * a[s]);
if (i > s)
upd(ans, dp[t][i] + lf[d - t - vis] + vis * a[s]);
}
return ans;
}
