Submission #112348

#	Time	Username	Problem	Language	Result	Execution time	Memory
112348		socho	Rice Hub (IOI11_ricehub)	C++14	68 / 100	1026 ms	2112 KiB

ricehub

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

int budget_handler;
int ricefield_count;
int len;
int arr[100001];

int summed_range(int left, int right) {
    //
    int median = arr[(left+right)/2];
    int sm = 0;
    for (int i=left; i<=right; i++) {
        sm += abs(arr[i] - median);
    }
    // cout << "from " << left << " to " << right << " gives: " << sm << endl;
    return sm;
}

int furthest_valid(int leftlock) {
    int low = leftlock;
    int high = ricefield_count;
    int 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 (int i=0; i<R; i++) {
        arr[i] = X[i];
    }

    int mx = 0;
    for (int i=0; i<R; i++) {
        int 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: 0 / 32