Submission #50940

#	Time	Username	Problem	Language	Result	Execution time	Memory
50940		win11905	Rice Hub (IOI11_ricehub)	C++11	0 / 100	6 ms	620 KiB

ricehub

#include "ricehub.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] * (m-l)) - (pref[m-1] - pref[l-1]);
		long long rhs = (pref[r] - pref[m]) - (pref[m] * (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: 0 / 17
• Subtask 2: 0 / 25
• Subtask 3: 0 / 26
• Subtask 4: 0 / 32