Submission #80513

#	Time	Username	Problem	Language	Result	Execution time	Memory
80513		arman_ferdous	Rice Hub (IOI11_ricehub)	C++17	51 / 100	954 ms	8216 KiB

ricehub

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

typedef long long ll;
ll n; ll place, cap;
vector<ll> v;

bool cmp(ll a, ll b) {
	return abs(a-place) < abs(b-place);
}

ll calc(ll x) {
	place = x;
	sort(v.begin(),v.end(),cmp);
	ll have = cap; ll ret = 0;
	for(ll i = 0; i < n; i++) {
		if(abs(v[i]-x) > have) break;
		have -= abs(v[i]-x);
		ret++;
	} return ret;
}

int besthub(int R, int L, int X[], ll B) {
	n = R; cap = B;
	for(ll i = 0; i < R; i++) v.push_back(X[i]);

	ll lo = 0, hi = L;
	while(hi - lo >= 30) {
		ll mid1 = (lo + lo + hi)/3;
		ll mid2 = (lo + hi + hi)/3;
		ll got1 = calc(mid1), got2 = calc(mid2);
		if(got1 > got2) hi = mid2 - 1;
		else lo = mid1 + 1;
	}
	ll ret = 0;
	for(ll i = lo; i <= hi; i++)
		ret = max(ret , calc(i));
	return ret;
}

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