Submission #115245

#	Time	Username	Problem	Language	Result	Execution time	Memory
115245		oolimry	Rice Hub (IOI11_ricehub)	C++14	17 / 100	26 ms	3976 KiB

ricehub

#include "ricehub.h"
#include <bits/stdc++.h>

using namespace std;
int besthub(int R, int L, int X[], long long B)
{
    vector<int> untaken;
    for(int i = 0;i < R;i++){
        untaken.push_back(X[i]);
    }
    untaken.push_back(4 * L);
    sort(untaken.begin(),untaken.end());
    reverse(untaken.begin(),untaken.end());
    deque<int> left, right; ///front-closest, back-furthest
    long long acc = 0;
    int ans = 0;
    for(int i = 1;i <= L;i++){
        bool stop = false;
        while(!right.empty() && right.front() == i-1){
            right.pop_front();
            left.push_front(i-1);
        }
        acc -= right.size();
        acc += left.size();

        while(true){
            if(acc > B){
                if(right.empty()){
                    acc -= abs(left.back() - i);
                    left.pop_back();
                }
                else if(left.empty()){
                    acc -= abs(right.back() - i);
                    untaken.push_back(right.back());
                    right.pop_back();
                    stop = true;
                }
                else{
                    if(abs(right.back() - i) > abs(left.back() - i)){
                        acc -= abs(right.back() - i);
                        untaken.push_back(right.back());
                        right.pop_back();
                        stop = true;
                    }
                    else{
                        acc -= abs(left.back() - i);
                        left.pop_back();
                    }
                }
            }
            else{
                if(stop) break;
                ans = max(ans, (int)(left.size() + right.size()));
                acc += abs(untaken.back() - i);
                right.push_back(untaken.back());
                untaken.pop_back();
            }
        }
    }
    return ans;
}

• Subtask 1: 17 / 17
• Subtask 2: 0 / 25
• Subtask 3: 0 / 26
• Subtask 4: 0 / 32