Submission #1278994

#	Time	Username	Problem	Language	Result	Execution time	Memory
1278994		IBory	Rice Hub (IOI11_ricehub)	C++20	100 / 100	9 ms	2632 KiB

ricehub

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

const int MAX = 100007;
ll X[MAX], PX[MAX];

bool Check(ll B, int R, int d) {
	ll g = 1e18, l;
	for (int i = 1; i + d <= R; ++i) {
		int j = i + d, mid = (i + j) / 2, left = mid - i + 1, right = j - mid + 1;
		l = (PX[j] - PX[mid - 1] - right * X[mid]) + left * X[mid] - PX[mid] + PX[i - 1];
		g = min(g, l);
	}
	return (g <= B);
}

int besthub(int R, int L, int* _X, ll B) {
	for (int i = 1; i <= R; ++i) X[i] = _X[i - 1];
	sort(X + 1, X + R + 1);
	for (int i = 1; i <= R; ++i) PX[i] = X[i] + PX[i - 1];

	int l = -1, r = R;
	while (l + 1 < r) {
		int mid = (l + r) / 2;
		(Check(B, R, mid) ? l : r) = mid;
	}

	return r;
}

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