#include "holiday.h"
#include <bits/stdc++.h>
using i64 = long long int;
constexpr i64 inf = 1ll << 50;
std::vector<i64> conv(std::vector<i64> a, std::vector<i64> b) {
const int n = (int)a.size(), m = (int)b.size();
std::vector<i64> c(n + m - 1, -inf);
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
c[i + j] = std::max(c[i + j], a[i] + b[j]);
}
}
return c;
}
std::vector<i64> solveSub(std::vector<i64> A) {
const int N = (int)A.size();
auto divConq = [&](auto &&self, const int l, const int r) -> std::vector<i64> {
if (r - l == 0) {
std::vector<i64> ret = {0};
return ret;
}
if (r - l == 1) {
std::vector<i64> ret = {0, 0, A[l]};
return ret;
}
const int m = (l + r) / 2;
std::vector<i64> lResRec = self(self, l, m);
std::vector<i64> rRes = self(self, m, r);
{
std::vector<i64> nrRes;
for (int i = 0; i <= m - l; ++i) {
nrRes.push_back(-inf);
}
std::copy(rRes.begin() + 1, rRes.end(), std::back_inserter(nrRes));
rRes = nrRes;
}
rRes[0] = -inf;
std::sort(A.begin() + l, A.begin() + m, std::greater());
std::vector<i64> lRes = {0};
std::copy(A.begin() + l, A.begin() + m, std::back_inserter(lRes));
for (int i = 1; i < (int)lRes.size(); ++i) {
lRes[i] += lRes[i - 1];
}
const auto fullRes = conv(lRes, rRes);
std::vector<i64> res(std::max(fullRes.size(), lResRec.size()));
for (int i = 0; i < std::max(fullRes.size(), lResRec.size()); ++i) {
const auto a = i < fullRes.size() ? fullRes[i] : -inf;
const auto b = i < lResRec.size() ? lResRec[i] : -inf;
res[i] = std::max(a, b);
}
return res;
};
return divConq(divConq, 0, N);
}
i64 solve(int n, int start, int d, std::vector<i64> attraction) {
std::vector<i64> lVec, rVec;
for (int i = start - 1; i >= 0; --i) {
lVec.push_back(attraction[i]);
}
for (int i = start; i < n; ++i) {
rVec.push_back(attraction[i]);
}
auto calc1 = [](std::vector<i64> vec) {
return solveSub(vec);
};
auto calc2 = [](std::vector<i64> vec) {
std::vector<i64> vec2;
for (const auto e : vec) {
vec2.push_back(0);
vec2.push_back(e);
}
return solveSub(vec2);
};
const auto l1 = calc1(lVec), l2 = calc2(lVec), r1 = calc1(rVec), r2 = calc2(rVec);
i64 answer = 0;
for (int i = 0; i <= d; ++i) {
const int a = i;
const int b = d - i + 2;
if (a < l1.size() and b < r2.size()) {
answer = std::max(answer, l1[a] + r2[b]);
}
}
for (int i = 0; i <= d; ++i) {
const int a = i;
const int b = d - i + 1;
if (a < l2.size() and b < r1.size()) {
answer = std::max(answer, l2[a] + r1[b]);
}
}
return answer;
}
long long int findMaxAttraction(int n, int start, int d, int attraction[]) {
std::vector<i64> atr(n);
for (int i = 0; i < n; ++i) {
atr[i] = attraction[i];
}
return solve(n, start, d, atr);
}
