Submission #1209455

#	Time	Username	Problem	Language	Result	Execution time	Memory
1209455		HappyCapybara	Holiday (IOI14_holiday)	C++20	100 / 100	705 ms	12640 KiB

holiday

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

#define ll long long

int n, d;
vector<int> a;
vector<ll> l1, l2, r1, r2;

void solve(int s, int k, vector<ll>& dp){
    dp[0] = 0;
    vector<int> opt(d+1);
    opt[0] = s;
    for (int j=16; j>=0; j--){
        ll cur = 0;
        priority_queue<ll> in, out;
        out.push(a[s]);
        for (int i=1<<j; i<=d; i+=1<<(j+1)){
            int l = opt[i-(1<<j)], r = i+(1<<j) <= d ? opt[i+(1<<j)] : n-1;
            pair<ll,int> bsf = {0, s};
            for (int loc=l; loc<=r; loc++){
                if (loc != l) out.push(a[loc]);
                int vis = i-k*(loc-s);
                if (vis < 0) continue;
                while (in.size() < vis && !out.empty()){
                    in.push(-out.top());
                    cur += out.top();
                    out.pop();
                }
                while (in.size() > vis){
                    cur += in.top();
                    out.push(-in.top());
                    in.pop();
                }
                while (!in.empty() && !out.empty() && -in.top() < out.top()){
                    cur += in.top();
                    cur += out.top();
                    out.push(-in.top());
                    in.pop();
                    in.push(-out.top());
                    out.pop();
                }
                bsf = max(bsf, {cur, loc});
            }
            dp[i] = bsf.first;
            opt[i] = bsf.second;
        }
    }
}

ll findMaxAttraction(int n, int start, int d, int attraction[]){
    ::n = n;
    ::d = d;
    a.resize(n);
    for (int i=0; i<n; i++) a[i] = attraction[i];
    r1.resize(d+1);
    r2.resize(d+1);
    l1.resize(d+1);
    l2.resize(d+1);
    solve(start, 1, r1);
    solve(start, 2, r2);
    a[start] = 0;
    reverse(a.begin(), a.end());
    start = n-1-start;
    solve(start, 1, l1);
    solve(start, 2, l2);
    ll res = 0;
    for (int i=0; i<=d; i++) res = max(res, max(l2[i]+r1[d-i], l1[i]+r2[d-i]));
    return res;
}

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