Submission #112351

#	Time	Username	Problem	Language	Result	Execution time	Memory
112351		socho	Rice Hub (IOI11_ricehub)	C++14	100 / 100	26 ms	3328 KiB

ricehub

#include "ricehub.h"
#include <bits/stdc++.h>
using namespace std;

long long budget_handler;
long long ricefield_count;
long long len;
long long arr[100001];
long long pf[100001];

void pfcompute() {
    pf[0] = arr[0];
    for (long long i=1; i<ricefield_count; i++) {
        pf[i] = arr[i] + pf[i-1];
    }
}

long long pfq(long long a, long long b) {
    if (a == 0) return pf[b];
    return pf[b] - pf[a-1];
}

long long summed_range(long long left, long long right) {
    //
    long long median = (left+right)/2;
    long long medscore = arr[median];
    long long sm = 0;
    // from left to median
    long long countl = median - left;
    long long suml = pfq(left, median-1);
    sm += (countl * medscore) - suml;
    // from median to right
    long long countr = right - median + 1;
    long long sumr = pfq(median, right);
    sm += sumr - (countr * medscore);
    return sm;
}

long long furthest_valid(long long leftlock) {
    long long low = leftlock;
    long long high = ricefield_count;
    long long mid;
    while (low + 1 < high) {
        mid = (low + high) / 2;
        if (summed_range(leftlock, mid) <= budget_handler) {
            low = mid;
        }
        else {
            high = mid;
        }
    }
    if (high != ricefield_count) {
        if (summed_range(leftlock, high) <= budget_handler) {
            return high;
        }
    }
    return low;
}

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

    budget_handler = B;
    len = L;
    ricefield_count = R;

    for (long long i=0; i<R; i++) {
        arr[i] = X[i];
    }

    pfcompute();

    long long mx = 0;
    for (long long i=0; i<R; i++) {
        long long besthere = furthest_valid(i);
        // cout << i << " : " << besthere << endl;
        mx = max(mx, besthere-i+1);
    }    

    return mx;
}

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