oj.uz

Submission #485188

# Submission time Handle Problem Language Result Execution time Memory
485188 2021-11-06T13:41:19 Z couplefire Holiday (IOI14_holiday) C++17
100 / 100
 1358 ms 12440 KB 
#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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 588 KB Output is correct
2 Correct 1 ms 588 KB Output is correct
3 Correct 0 ms 588 KB Output is correct
4 Correct 1 ms 588 KB Output is correct
5 Correct 1 ms 588 KB Output is correct
6 Correct 1 ms 588 KB Output is correct
7 Correct 0 ms 588 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 270 ms 8964 KB Output is correct
2 Correct 207 ms 9160 KB Output is correct
3 Correct 294 ms 9184 KB Output is correct
4 Correct 198 ms 9140 KB Output is correct
5 Correct 807 ms 6024 KB Output is correct
6 Correct 372 ms 7496 KB Output is correct
7 Correct 530 ms 4136 KB Output is correct
8 Correct 522 ms 3976 KB Output is correct
9 Correct 264 ms 10208 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 972 KB Output is correct
2 Correct 8 ms 928 KB Output is correct
3 Correct 9 ms 972 KB Output is correct
4 Correct 18 ms 800 KB Output is correct
5 Correct 18 ms 844 KB Output is correct
6 Correct 3 ms 716 KB Output is correct
7 Correct 3 ms 588 KB Output is correct
8 Correct 3 ms 588 KB Output is correct
9 Correct 3 ms 588 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 289 ms 12440 KB Output is correct
2 Correct 1358 ms 10664 KB Output is correct
3 Correct 122 ms 1188 KB Output is correct
4 Correct 8 ms 716 KB Output is correct
5 Correct 3 ms 588 KB Output is correct
6 Correct 3 ms 588 KB Output is correct
7 Correct 3 ms 588 KB Output is correct
8 Correct 633 ms 2792 KB Output is correct
9 Correct 626 ms 2628 KB Output is correct