Submission #50946

#	Time	Username	Problem	Language	Result	Execution time	Memory
50946		win11905	Rice Hub (IOI11_ricehub)	C++11	100 / 100	33 ms	15996 KiB

ricehub

#include "ricehub.h"
#include <stdio.h>

const int N = 1e5+5;

long long pref[N];

int besthub(int R, int L, int X[], long long B) {
	for(int i = 0; i < R; ++i) pref[i+1] = pref[i] + X[i];
	auto f = [&](int l, int r, int m) {
		long long lhs = ((pref[m] - pref[m-1]) * (m-l)) - (pref[m-1] - pref[l-1]);
		long long rhs = (pref[r] - pref[m]) - ((pref[m] - pref[m-1]) * (r - m));
		return lhs + rhs <= B;
	};
	int l = 1, r = R;
	while(l < r) {
		int m = (l + r + 1) >> 1;
		bool st = false;
		for(int x = 1, y = m; y <= R; x++, y++) {
			int z = (x + y) >> 1;
			st |= f(x, y, z);
		}
		if(st) l = m;
		else r = m - 1;
	}
	return l;
}

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