#include "holiday.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
long long sub2(int32_t n, int32_t start, int32_t d, int32_t attraction[]) {
priority_queue<int, vector <int>, greater<int>> pq;
int i;
int sum = 0;
if (d % 2 == 1) {
for (i = 0;i < min((d + 1) / 2, n);i++) {
sum += attraction[i];
pq.push(attraction[i]);
}
int cnt = 0;
int ans = sum;
while (pq.size() > 0 && i < n) {
int x = pq.top();
// cout << x << "\n";
sum -= x;
pq.pop();
cnt ^= 1;
if (cnt) {
continue;
}
sum += attraction[i];
pq.push(attraction[i]);
ans = max(ans, sum);
i++;
}
return ans;
}
else {
for (i = 0;i < min((d + 1) / 2, n);i++) {
sum += attraction[i];
pq.push(attraction[i]);
}
int cnt = 0;
int ans = sum;
while (pq.size() > 0 && i < n) {
int x = pq.top();
// cout << x << "\n";
sum -= x;
pq.pop();
cnt ^= 1;
if (!cnt) {
continue;
}
sum += attraction[i];
pq.push(attraction[i]);
ans = max(ans, sum);
i++;
}
return ans;
}
return 0;
}
long long maxSum(priority_queue <int> pq1, int req) {
long long res = 0;
while (req > 0 && !pq1.empty()) {
res += pq1.top();
req--;
pq1.pop();
}
return res;
}
long long findMaxAttraction(int32_t n, int32_t start, int32_t d, int32_t attraction[]) {
int mx = 0;
for (int i = 0;i < n;i++) {
mx = max(mx, 1ll * attraction[i]);
}
if (mx <= 100 && start == 0) {
return sub2(n, start, d, attraction);
}
priority_queue <int> pq;
long long res = 0;
for (int l = start;l >= 0;l--) {
pq.push(attraction[l]);
priority_queue <int> pq1 = pq;
int req = d - (start - l);
if (req < 0) break;
res = max(res, maxSum(pq1, req));
for (int r = start + 1;r < n;r++) {
pq1.push(attraction[r]);
int req = d - (r - l + min(start - l, r - start));
if (req < 0) break;
res = max(res, maxSum(pq1, req));
}
}
return res;
}
