#include "holiday.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
long long line(int d, vector<ll> attract)
{
if (d<=0)
return 0;
int n = attract.size();
while (n<=d)
{
attract.push_back(0);
n++;
}
priority_queue<ll, vector<ll>, greater<ll>> stops;
//d++;//cost of starting = 1, so that collecting cost is 2 and skipping cost is 1
int choices = 0;
ll total = 0;
ll best = 0;
for (int explore = 0; explore<d; explore++)
{
//cout << attract[explore] << '\n';
stops.push(attract[explore]);
choices++;
total += attract[explore];
while ((choices+explore)>d)
{
choices--;
ll x = stops.top();
total -= x;
stops.pop();
}
best = max(best, total);
}
//cout << best << '\n';
return best;
}
long long int findMaxAttraction(int n, int start, int d, int attraction[]) {
vector<ll> attract(n);
for (int i=0; i<n; i++)
attract[i] = attraction[i];
ll super_best = 0;
for (int i=0; i<=start; i++)
{
int days_available = d-start+i;
vector<ll> new_attract;
for (int j=i; j<n; j++)
new_attract.push_back(attract[j]);
super_best = max(super_best, line(days_available, new_attract));
}
for (int i=start; i<n; i++)
{
int days_available = d-(i-start);
vector<ll> new_attract;
for (int j=i; j>=0; j--)
new_attract.push_back(attract[j]);
super_best = max(super_best, line(days_available, new_attract));
}
return super_best;
}
