Submission #1065925

#	Time	Username	Problem	Language	Result	Execution time	Memory
1065925		jer033	Holiday (IOI14_holiday)	C++17	23 / 100	25 ms	5424 KiB

holiday

#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);
}

• Subtask 1: 0 / 7
• Subtask 2: 23 / 23
• Subtask 3: 0 / 17
• Subtask 4: 0 / 53