Submission #228559

#	Time	Username	Problem	Language	Result	Execution time	Memory
228559		tushar_2658	Rice Hub (IOI11_ricehub)	C++14	68 / 100	1092 ms	2560 KiB

ricehub

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

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

ll a[maxn], lim;
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;
		for(int j = l; j <= i; ++j){
			need += llabs(a[j] - a[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];
	}
	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: 0 / 32