Submission #146599

#	Time	Username	Problem	Language	Result	Execution time	Memory
146599		MathStudent2002	Rice Hub (IOI11_ricehub)	C++14	100 / 100	20 ms	3452 KiB

ricehub

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

using namespace std;

typedef long long ll;

const int MAXR = 100005;
const ll INFTY = 1000000000000000007;

ll Rval;
ll loc[MAXR];
ll psum[MAXR];

void init() {
    psum[0] = 0;
    for(int i = 1; i <= Rval; i++) {psum[i] = psum[i-1] + loc[i];}
}

ll quer(int l, int r) {
    return psum[r] - psum[l-1];
}

ll mincost(int P) { // minimum cost of P paddies
    ll ans = INFTY;
    for(int i = 0; i+P <= Rval; i++) {//checking i+1...i+P
        ans = min(ans, quer(i+1+P-P/2, i+P) - quer(i+1, i+P/2));
    }
    return ans;
}

int besthub(int R, int L, int X[], long long B) {
    Rval = R;
    for(int i = 0; i < R; i++) {loc[i+1] = X[i];}
    init();
    int lo = 1, hi = R;
    int mi;
    while(lo != hi) {
        mi = (lo+hi+1)/2;
        if(mincost(mi) <= B) {lo = mi;}
        else {hi = mi-1;}
    }

    return lo;
}

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