Submission #1270986

#	Time	Username	Problem	Language	Result	Execution time	Memory
1270986		cmiuc	Rice Hub (IOI11_ricehub)	C++20	100 / 100	151 ms	2388 KiB

ricehub

#include <iostream>
#include <algorithm>
#include "ricehub.h"

using namespace std;
long long suf[1<<17], pre[1<<17];

int besthub(int n, int L, int x[], long long B){
	for (int i=n-1;i>=0;i--)
		suf[i] = suf[i + 1] + x[i];
		
	int Ans = 0;
	for (int i=0;i<n;i++){
		pre[i] = (i == 0 ? 0 : pre[i-1]) + x[i];

		long long l = -1, r = L + 1, lft, rgt, cst;
		while (l + 1 < r){
			int mid = (l + r) / 2;
			int k2 = upper_bound(x + i, x + n, x[i] + mid) - x;
			int k1 = upper_bound(x, x + n, x[i] - mid - 1) - x;

			long long nB = (suf[i] - suf[k2]) - 1LL * (k2 - i) * x[i];
			nB = 1LL * (i - k1 + 1) * x[i] - (pre[i] - (k1 == 0 ? 0 : pre[k1-1])) + nB;

			if (nB <= B)
				l = mid, lft = k1, rgt = k2, cst = nB;
			else
				r = mid;
		}

		long long mn = B + 1;
		if (lft > 0)
			mn = x[i] - x[lft - 1];
		if (rgt < n)
			mn = min(mn, 0LL + x[rgt] - x[i]);
		Ans = max(Ans + 0LL, rgt - lft + (B - cst) / mn);
	}
	return Ans;
}

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