#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++)
{
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);
}
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];
return line(d, attract);
}
