#include "holiday.h"
#include <bits/stdc++.h>
using namespace std;
long long int sub2(int n, int start, int d, int 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 int findMaxAttraction(int n, int start, int d, int attraction[]) {
int mx = 0;
for (int i = 0;i < n;i++) {
mx = max(mx, attraction[i]);
}
if (mx <= 100 && start == 0) {
return sub2(n, start, d, attraction);
}
return 0;
}
