#include "holiday.h"
#include <bits/stdc++.h>
using i64 = long long int;
constexpr i64 inf = 1ll << 50;
template <class F>
std::vector<int> smawk(int rs, int cs, const F &select) {
auto solve = [&](auto &&self, std::vector<int> row, std::vector<int> col) -> std::vector<int> {
const int n = (int)row.size();
if (n == 0) {
return {};
}
std::vector<int> c2, r2;
for (const int i : col) {
while ((not c2.empty()) and select(row[c2.size() - 1], c2.back(), i)) {
c2.pop_back();
}
if ((int)c2.size() < n) {
c2.push_back(i);
}
}
for (int i = 1; i < n; i += 2) {
r2.push_back(row[i]);
}
const auto a2 = self(self, r2, c2);
std::vector<int> ret(n);
for (int i = 0; i < (int)a2.size(); ++i) {
ret[2 * i + 1] = a2[i];
}
int j = 0;
for (int i = 0; i < n; i += 2) {
ret[i] = c2[j];
const int ed = i + 1 == n ? c2.back() : ret[i + 1];
while (c2[j] != ed) {
if (select(row[i], ret[i], c2[++j])) {
ret[i] = c2[j];
}
}
}
return ret;
};
std::vector<int> row(rs), col(cs);
std::iota(row.begin(), row.end(), 0);
std::iota(col.begin(), col.end(), 0);
return solve(solve, row, col);
}
std::vector<i64> plusMaxConvolution(const std::vector<i64> a, const std::vector<i64> b) {
const int n = (int)a.size(), m = (int)b.size();
const auto get = [&](const int i, const int j) {
return a[j] + b[i - j];
};
const auto select = [&](const int i, const int j, const int k) {
if (i < k) {
return false;
}
if (i - j >= m) {
return true;
}
return get(i, j) <= get(i, k);
};
const auto amax = smawk(n + m - 1, n, select);
std::vector<i64> ret(n + m - 1);
for (int i = 0; i < n + m - 1; ++i) {
ret[i] = get(i, amax[i]);
}
return ret;
}
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 = std::move(nrRes);
}
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 = plusMaxConvolution(rRes, lRes);
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);
}
std::vector<i64> newA;
std::merge(A.begin() + l, A.begin() + m, A.begin() + m, A.begin() + r, std::back_inserter(newA), std::greater());
std::copy(newA.begin(), newA.end(), A.begin() + l);
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;
answer = std::max(answer, l1[std::min((int)l1.size() - 1, a)] + r2[std::min((int)r2.size() - 1, b)]);
}
for (int i = 0; i <= d; ++i) {
const int a = i;
const int b = d - i + 1;
answer = std::max(answer, l2[std::min((int)l2.size() - 1, a)] + r1[std::min((int)r1.size() - 1, 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);
}
