#include <bits/stdc++.h>
#include "holiday.h"
using namespace std;
using ll = long long;
using pii = pair<int, int>;
const int mxN = 3000+5;
//0 -> derecha, puedo tomar
//1 ->derecha, no puedo tomar
//2 -> devolviendome, puedo tomar si j<s
//3 -> devolviendome, no puedo tomar aunque j<s
ll memo[mxN][3*mxN][4];
vector<int> a;
int d, s;
ll f(int i, int j, int k) {
//memo[i][j] = mejor respuesta al estar en ciudad i tras j dias
if (j > d) return 0;
if (i>=(int)a.size() || i<0) return -1e18;
if (memo[i][j][k] != -1) return memo[i][j][k];
ll result;
if (k>=2) {
ll caso1 = f(i-1, j+1, 2);
ll caso2 = 0;
if (k==2 && i<s) caso2 = a[i]+f(i, j+1, 3);
result = max(caso1, caso2);
}
else {
//derecha
ll caso1 = f(i+1, j+1, 0);
ll caso2=0;
if (k==0) caso2 = a[i]+f(i, j+1, 1);
ll caso3 = f(i-1, j+1, 2); //Moverme a la izq
result = max({
caso1, caso2, caso3
});
}
//cout << i << " " << j << " " << k << " " << result << endl;
return memo[i][j][k] = result;
}
ll findMaxAttraction(int n, int S, int D, int A[]) {
s = S;
d = D;
a.assign(n, 0);
for (int i=0; i<n; i++) {
a[i] = A[i];
}
memset(memo, -1, sizeof(memo));
return f(s, 1, 0);
}
