Submission #485188

#	Time	Username	Problem	Language	Result	Execution time	Memory
485188		couplefire	Holiday (IOI14_holiday)	C++17	100 / 100	1358 ms	12440 KiB

holiday

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

vector<ll> calc(int start, int attraction[], array<int, 4> init, bool type){
    if(init[1]<0) return {};
    if(start>init[3]) return vector<ll>(init[1]+1, 0ll);
    vector<ll> f(init[1]+1);
    vector<array<int, 4>> level = {init}; // l, r, optl, optr
    while(level.size()){
        vector<array<int, 4>> newlevel;
        priority_queue<int, vector<int>, greater<>> in;
        priority_queue<int> out; int curpos;
        if(type) curpos = start-1;
        else curpos = start+1;
        ll cursum = 0;
        auto addAttraction = [&](int pos){
            while(curpos!=pos){
                if(curpos<pos) ++curpos;
                else --curpos; 
                int val = attraction[curpos];
                if(in.empty() || val<in.top()) out.push(val);
                else out.push(in.top()), cursum -= in.top(), in.pop(), in.push(val), cursum += val;
            }
        };
        auto add = [&](int target){
            while(!out.empty() && (int)in.size()<target)
                in.push(out.top()), cursum += out.top(), out.pop();
        };
        auto del = [&](int target){
            while(!in.empty() && (int)in.size()>target)
                out.push(in.top()), cursum -= in.top(), in.pop();
        };
        auto change = [&](int target){
            if((int)in.size()<target) add(target);
            else del(target);
        };
        for(auto [l, r, optl, optr] : level){
            int avail = (l+r)>>1;
            ll best = -1; int pos = optl;
            if(type){
                for(int i = optl; i<=optr; ++i){
                    addAttraction(i);
                    change(avail-(i-start));
                    if(cursum>best) best = cursum, pos = i;
                }
            } else{
                for(int i = optr; i>=optl; --i){
                    addAttraction(i);
                    change(avail-2*(start-i));
                    if(cursum>best) best = cursum, pos = i;
                }
            }
            f[avail] = best;
            if(type){
                if(avail>l) newlevel.push_back({l, avail-1, optl, pos});
                if(avail<r) newlevel.push_back({avail+1, r, pos, optr});
            } else{
                if(avail>l) newlevel.push_back({l, avail-1, pos, optr});
                if(avail<r) newlevel.push_back({avail+1, r, optl, pos});
            }
        }
        swap(level, newlevel);
    }
    return f;
}

ll solve(int n, int start, int d, int attraction[]){
    vector<ll> f = calc(start+1, attraction, {0, d-1, start+1, n-1}, 1);
    f.insert(f.begin(), 0);
    vector<ll> g = calc(start, attraction, {0, d, 0, start}, 0);
    ll ans = 0;
    for(int i = 0; i<=d; ++i)
        ans = max(ans, g[i]+f[d-i]);
    return ans;
}

ll findMaxAttraction(int n, int start, int d, int attraction[]){
    ll ans1 = solve(n, start, d, attraction);
    for(int i = 0; i<n/2; ++i)
        swap(attraction[i], attraction[n-1-i]);
    start = n-1-start;
    ll ans2 = solve(n, start, d, attraction);
    return max(ans1, ans2);
}

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