Submission #228561

#	Time	Username	Problem	Language	Result	Execution time	Memory
228561		tushar_2658	Rice Hub (IOI11_ricehub)	C++14	100 / 100	26 ms	3328 KiB

ricehub

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

const int maxn = 100005;
using ll = long long;

ll a[maxn], lim, p[maxn];
int n;

bool can(int x){
	ll ret = LLONG_MAX;
	for(int i = x; i <= n; ++i){
		int l = i - x + 1;
		ll mid = (l + (x / 2));
		ll need = 0;
		need += (a[mid] * (mid - l + 1)) - (p[mid] - p[l - 1]);
		need += (p[i] - p[mid]) - (a[mid] * (i - mid));
		ret = min(ret, need);
	}
	if(ret <= lim)return 1;
	else return 0;
}

int besthub(int R, int L, int X[], long long B)
{
	lim = B;
	n = R;
	for(int i = 1; i <= R; ++i){
		a[i] = X[i - 1];
	}
	for(int i = 1; i <= R; ++i){
		p[i] = p[i - 1] + a[i];
	}
	sort(a + 1, a + n + 1);
	int lo = 1, hi = R, ans = 1;
	while(lo <= hi){
		int mid = (lo + hi) >> 1;
		if(can(mid)){
			ans = mid;
			lo = mid + 1;
		}else {
			hi = mid - 1;
		}
	}
	return ans;
}

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