Submission #253351

#	Time	Username	Problem	Language	Result	Execution time	Memory
253351		eohomegrownapps	Holiday (IOI14_holiday)	C++14	47 / 100	5090 ms	2752 KiB

holiday

#include"holiday.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll findMaxFrom(int n, int start, int d, int attraction[]){
    //from start
    int numwalk = d/2;
    int numtake = d-numwalk;
    priority_queue<ll,vector<ll>,greater<ll>> pq;
    ll tot = 0;
    ll ans = 0;
    for (int i = start; i<=min(n-1,start+numwalk); i++){
        tot+=attraction[i];
        pq.push(attraction[i]);
    }
    if (numtake==numwalk&&start+numwalk<=n-1){
        tot-=pq.top();
        pq.pop();
    }
    ans=max(ans,tot);
    int cur = start+numwalk;
    while (cur<n-1&&numtake>0&&numwalk<d){
        //walk one more
        numtake--;
        numwalk++;
        cur++;
        tot+=attraction[cur];
        pq.push(attraction[cur]);
        tot-=pq.top();
        pq.pop();
        tot-=pq.top();
        pq.pop();
        ans=max(ans,tot);
    }
    return ans;
}

ll findMaxAttraction(int n, int start, int d, int attraction[]) {
    ll mx = 0;
    for (int i = max(0,start-d); i<=start; i++){
        mx=max(mx,findMaxFrom(n,i,d-(start-i),attraction));
    }
    if (n>5000){
        return mx;
    }
    reverse(attraction,attraction+n);
    start=n-1-start;
    for (int i = max(0,start-d); i<=start; i++){
        mx=max(mx,findMaxFrom(n,i,d-(start-i),attraction));
    }
    return mx;
}

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