Submission #1065956

#	Time	Username	Problem	Language	Result	Execution time	Memory
1065956		jer033	Holiday (IOI14_holiday)	C++17	47 / 100	983 ms	6444 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++)
    {
        //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];
    if (n>3000)
        return line(d, attract);
    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;
}

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