#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];
}
vector<ll> dpright(d+1, 0);
vector<ll> dpleft(d+1, 0);
for (int i=s-1; i>=0; i--) {
for (int j=d; j>=s-i+1; j--) {
dpleft[j] = max(dpleft[j], dpleft[j-1]);
if (j>=2) dpleft[j] = max(dpleft[j], dpleft[j-2]+a[i]);
}
}
dpright[0] = 0;
dpright[1] = a[s];
ll ans=0;
for (int i=2; i<=d; i++) {
dpright[i] = dpright[i-1];
ans = max(ans, dpright[i] + dpleft[d-i]);
}
for (int i=s+1; i<n; i++) {
for (int j=d; j>=i-s+1; j--) {
dpright[j] = dpright[j-1];
if (j>=2) dpright[j] = max(dpright[j], dpright[j-2]+a[i]);
}
for (int j=d; j>=i-s+1; j--) {
if (d-j-(i-s+1) < 0) continue;
ans = max(ans, dpright[j]+dpleft[d-j-(i-s)]);
}
}
return ans;
}
