#include"holiday.h"
#include <bits/stdc++.h>
using namespace std;
const long long inf = 1e18L + 20;
vector<long long> calc(vector<int> a) {
int n = a.size();
vector<long long> res(n * 2 + 1);
if (n == 0) {
return res;
}
if (n == 1) {
res[2] = a[0];
return res;
}
vector<int> left(a.begin(), a.begin() + n / 2);
vector<int> right(a.begin() + n / 2, a.end());
vector<long long> best_l = calc(left);
vector<long long> best_r = calc(right);
for (int i = 0; i <= (n / 2) * 2; i++) {
res[i] = best_l[i];
}
for (int i = 0; i < n / 2; i++) {
best_l[i] = -inf;
}
best_l[n / 2] = 0;
sort(left.begin(), left.end(), greater<int>());
for (int i = n / 2 + 1; i <= (n / 2) * 2; i++) {
best_l[i] = best_l[i - 1] + left[i - n / 2 - 1];
}
for (int i = n / 2; i <= (n / 2) * 2; i++) {
for (int j = 0; j <= (n - n / 2) * 2; j++) {
res[i + j] = max(res[i + j], best_l[i] + best_r[j]);
}
}
return res;
}
long long solve(int n, int start, int d, int attraction[]) {
vector<int> left(start * 2);
for (int i = 0; i < start; i++) {
left[i * 2] = 0;
left[i * 2 + 1] = attraction[start - 1 - i];
}
vector<int> right(n - 1 - start);
for (int i = start + 1; i < n; i++) {
right[i - start - 1] = attraction[i];
}
vector<long long> best_l = calc(left);
vector<long long> best_r = calc(right);
best_l.resize(d + 1);
best_r.resize(d + 1);
for (int i = 1; i <= d; i++) {
best_l[i] = max(best_l[i], best_l[i - 1]);
best_r[i] = max(best_r[i], best_r[i - 1]);
}
long long res = 0;
for (int i = 0; i <= d; i++) {
res = max(res, best_l[i] + best_r[d - i]);
}
for (int i = 0; i <= d - 1; i++) {
res = max(res, best_l[i] + best_r[d - 1 - i] + attraction[start]);
}
return res;
}
long long findMaxAttraction(int n, int start, int d, int attraction[]) {
long long res1 = solve(n, start, d, attraction);
for (int i = 0; i < n - 1 - i; i++) {
swap(attraction[i], attraction[n - 1 - i]);
}
start = n - 1 - start;
long long res2 = solve(n, start, d, attraction);
return max(res1, res2);
}
