Submission #760621

#	Time	Username	Problem	Language	Result	Execution time	Memory
760621		SanguineChameleon	Rice Hub (IOI11_ricehub)	C++17	100 / 100	160 ms	2920 KiB

ricehub

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

const int maxN = 1e5 + 20;
int a[maxN];
long long pref[maxN];

int besthub(int N, int L, int X[], long long B) {
	for (int i = 1; i <= N; i++) {
		a[i] = X[i - 1];
		pref[i] = pref[i - 1] + a[i];
	}
	int res = 0;
	for (int i = 1; i <= N; i++) {
		int lt = 0;
		int rt = L;
		int lim = -1;
		int cnt = -1;
		long long cost = -1;
		while (lt <= rt) {
			int mt = (lt + rt) / 2;
			int li = lower_bound(a + 1, a + N + 1, a[i] - mt) - a;
			int ri = upper_bound(a + 1, a + N + 1, a[i] + mt) - a - 1;
			long long cost_l = 1LL * a[i] * (i - li) - (pref[i - 1] - pref[li - 1]);
			long long cost_r = (pref[ri] - pref[i]) - 1LL * a[i] * (ri - i);
			if (cost_l + cost_r <= B) {
				cost = cost_l + cost_r;
				cnt = ri - li + 1;
				lim = mt;
				lt = mt + 1;
			}
			else {
				rt = mt - 1;
			}
		}
		if (lim < L) {
			cnt += (B - cost) / (lim + 1);
		}
		res = max(res, cnt);
	}
	return res;
}

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