Submission #1193136

#	Time	Username	Problem	Language	Result	Execution time	Memory
1193136		Nomio	Rice Hub (IOI11_ricehub)	C++20	100 / 100	13 ms	2632 KiB

ricehub

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

int besthub(int R, int L, int X[], ll B) {
	int ans = 0;
	vector<int> x(R + 1);
	for(int i = 0; i < R; i++) {
		x[i + 1] = X[i];
	}
	vector<ll> pre(R + 1, 0), suf(R + 2, 0);
	for(int i = 1; i <= R; i++) {
		pre[i] = pre[i - 1] + x[i];
	}
	for(int i = R; i >= 1; i--) {
		suf[i] = suf[i + 1] + x[i];
	}
	for(int i = 1; i <= R; i++) {
		int l = 0, r = R - i + 1;
		while(l < r) {
			int mid = (l + r + 1) / 2;
			int med = i + mid / 2;
			int cnta = med - i;
			int cntb = mid - cnta - 1;
			int ida = i;
			int idb = i + mid - 1;
			ll P = 1LL * cnta * x[med];
			P -= (pre[med - 1] - pre[ida - 1]);
			ll S = suf[med + 1] - suf[idb + 1];
			S -= 1LL * cntb * x[med];
			if(P + S <= B) l = mid;
			else r = mid - 1;
		}
		ans = max(ans, l);
	}
	return ans;
}
//
//int main() {
//	cout << besthub(5, 20, {1, 2, 10, 12, 14}, 6) << '\n';
//}

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