Submission #969914

#	Time	Username	Problem	Language	Result	Execution time	Memory
969914		urieg	Rice Hub (IOI11_ricehub)	C++17	74 / 100	14 ms	5212 KiB

ricehub

#include <bits/stdc++.h>
#include "ricehub.h"
using namespace std;
typedef long long ll;
/// for moondance

int besthub(int R, int L, int X[], long long B){

    vector<ll>x(R), p(R);
    for(int i=0;i<R;i++){
        x[i] = X[i];
        p[i] = x[i];
        if(i)p[i] += p[i-1];
    }

    ll sum = 0;
    int l = 1, r = R;
    while(l<r){
        int m = (l+r+1)/2;
        bool ok = 0;
        for(int i = 0;i+m<=R; i++){
            int L = i, R = i+m-1;
            int mid = (R+L)/2;
            sum = p[R] - p[mid] - (x[mid]*(R-mid));
            sum += x[mid]*(mid-L+1) - (!L ? 0 : p[mid]-p[L-1]);
//            cout<<L<<' '<<R<<' '<<mid<<' '<<sum<<endl;
            if(sum <= B){
                ok = 1;
                break;
            }
        }
//        cout<<m<<' '<<ok<<endl;
        if(ok){
            l = m;
        }
        else r = m-1;
    }
    return l;
}

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