#include"holiday.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 3003;
int a[N], val[N];
int n, d, s;
long long int findMaxAttraction(int n_, int start_, int d_, int attraction[]) {
n = n_;
d = d_;
s = start_;
for (int i = 0; i < n; ++i) {
a[i] = attraction[i];
}
long long ans = (d ? a[s] : 0);
long long cur = 0;
multiset<int> se;
auto add = [&](int x) {
se.insert(x);
cur += x;
};
auto Shrink = [&](int sz) {
while ((int) se.size() > sz) {
cur -= *se.begin();
se.erase(se.begin());
}
};
for (int i = s - 1; i >= 0; --i) {
for (int j = s - 1; j >= i; --j) {
add(a[j]);
}
int dis = s - i;
for (int j = s; j < n; ++j) {
int dis2 = j - s;
if (2 * dis + dis2 > d) {
break;
}
add(a[j]);
Shrink(d - (2 * dis + dis2));
ans = max(ans, cur);
}
cur = 0;
se.clear();
}
for (int i = s + 1; i < n; ++i) {
for (int j = s + 1; j <= i; ++j) {
add(a[j]);
}
int dis = i - s;
for (int j = s; j >= 0; --j) {
int dis2 = s - j;
if (2 * dis + dis2 > d) {
break;
}
add(a[j]);
Shrink(d - (2 * dis + dis2));
ans = max(ans, cur);
cout << i << ' ' << j << ' ' << 2 * dis + dis2 << ' ' << cur << '\n';
}
cur = 0;
se.clear();
}
return ans;
}
