Submission #833003

#	Time	Username	Problem	Language	Result	Execution time	Memory
833003		Halym2007	Rice Hub (IOI11_ricehub)	C++11	100 / 100	12 ms	4140 KiB

ricehub

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

int besthub(int R, int L, int X[], ll B) {
	vector <ll> arr(R + 1, 0), p(R + 1, 0), pr(R + 2, 0);
	for (int i = 0; i < R; ++i) {
		arr[i + 1] = X[i];
	}
	for (ll i = 1; i <= R; ++i) {
		p[i] = (arr[i] - arr[i - 1]) * (i - 1) + p[i - 1];
	}
	
	for (ll i = R; i > 0; i--) {
		pr[i] = (arr[i + 1] - arr[i]) * (R - i) + pr[i + 1];
	}
	ll l = 1, r = 1, jogap = 1;
	while (l <= R and r <= R) {
		ll md = (l + r + 1) / 2; 
		ll sum = p[md] - p[l - 1] - ((l - 1) * (arr[md] - arr[l - 1])); 
		ll sum1 = pr[md] - pr[r + 1] - ((R - r) * (arr[r + 1] - arr[md])); // yalnysh su
		ll sum2 = sum + sum1;
		if (sum2 <= B) {
			r++;
		}
		else {
			// l r -1 
			jogap = max (jogap, r - l);
			l++;
		}
	}
	jogap = max (jogap, r - l);
	return jogap;
}	

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