Submission #228394

#	Time	Username	Problem	Language	Result	Execution time	Memory
228394		tushar_2658	Rice Hub (IOI11_ricehub)	C++14	17 / 100	1087 ms	1920 KiB

ricehub

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

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

int a[maxn];
ll lim;
vector<ll> p;
int n;

bool can(int x){
	ll tot = LLONG_MAX;
	for(int i = x - 1; i < n; ++i){
		int l = i - x + 1;
		ll val;
		if(l != 0){
			val = p[i] - p[l - 1];
		}else {
			val = p[i];
		}
		val /= x;
		ll need = 0;
		for(int j = l; j <= i; ++j){
			need += llabs(a[j] - val);
		}
		tot = min(tot, need);
		need = 0;
		for(int j = l; j <= i; ++j){
			need += llabs(a[j] - (val + 1));
		}
		tot = min(tot, need);
	}
	if(tot <= lim)return 1;
	else return 0;
}

int besthub(int R, int L, int X[], long long B)
{
	n = R;
	lim = B;
	p.resize(R);
	for(int i = 0; i < R; ++i){
		a[i] = X[i];
	}
	sort(a, a + R);
	for(int i = 0; i < R; ++i){
		if(i == 0){
			p[i] = a[i];
		}else {
			p[i] = p[i - 1] + a[i];
		}
	}
  int ans = 0;
  int lo = 1, hi = R;
  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: 0 / 25
• Subtask 3: 0 / 26
• Subtask 4: 0 / 32