Submission #115275

#	Time	Username	Problem	Language	Result	Execution time	Memory
115275		oolimry	Rice Hub (IOI11_ricehub)	C++14	68 / 100	1073 ms	166904 KiB

ricehub

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

using namespace std;

int besthub(int R, int L, int X[], long long B)
{
    static long long pre[100005];
    pre[0] = X[0];
    for(int i = 1;i < R;i++){
        pre[i] = pre[i-1] + X[i];
    }
    long long ans = 0;
    int lrs[L+1];
    int rls[L+1];
    for(int pos = 1;pos <= L;pos++){
        lrs[pos] = lower_bound(X,X+R,pos) - X;
        rls[pos] = upper_bound(X,X+R,pos) - X;
    }
    for(int pos = 1;pos <= L;pos++){
        int lr = lrs[pos];
        int rl = rls[pos];
        int low = 0;
        int high = min(lr + 2, R - rl + 2);

        //cout << pos << " " << lr << " " << rl << " ";
        while(true){
            if(low == high - 1) break;
            int s = (low + high) / 2;
            int ll = lr - s;
            int rr = rl + s;
            if(ll < 0 || rr >= R){
                high = s;
                continue;
            }

            long long sum = 0ll;
            sum += pre[lr-1];
            if(ll > 0) sum -= pre[ll-1];
            sum = s * pos - sum;
            sum += pre[rr-1];
            sum -= pre[rl-1];
            sum -= s * pos;
            //cout << "\n" << pos << " " << sum << " " << s << "wow\n";
            if(sum > B){
                high = s;
            }
            else{
                low = s;
            }
        }
        int ll = lr - low;
        int rr = rl + low;
        long long sum = 0ll;
        if(lr > 0) sum += pre[lr-1];
        if(ll > 0) sum -= pre[ll-1];
        sum = low * pos - sum;
        if(rr > 0) sum += pre[rr-1];
        if(rl > 0) sum -= pre[rl-1];
        //assert(lr-1 >= 0);
        //assert(rr-1 >= 0);
        //assert(rl-1 >= 0);
        sum -= low * pos;
        long long nos = rr - ll;
        ans = max(nos, ans);
        if(ll > 0 && sum + (long long)(abs(pos - X[ll-1])) <= B){
            ans = max(nos+1,ans);
        }
        if(rr < R && sum + (long long)(abs(pos - X[rr])) <= B){
            ans = max(nos+1,ans);
        }
        //cout << low << "\n";
    }
    return ans;
}

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