Submission #253387

#	Time	Username	Problem	Language	Result	Execution time	Memory
253387		ChrisT	Rice Hub (IOI11_ricehub)	C++17	100 / 100	31 ms	2560 KiB

ricehub

#include<bits/stdc++.h>
#include "ricehub.h"
using namespace std;
int besthub (int r, int l, int *x, long long b) {
	vector<long long> psa(r);
	auto get = [&] (int pos) {
		return pos < 0 ? 0LL : psa[pos];
	};
	for (int i = 0; i < r; i++) psa[i] = get(i-1) + x[i];
	int ret = 0;
	for (int i = 0; i < r; i++) { //i^{th} is the median
		int low = 1, high = min(r,min(i+1,r-i) * 2), mid, ans = 0;
		while (low <= high) {
			mid = (low + high) / 2;
			int take = (mid - 1) / 2;
			long long go = get(i - take - 1) + get(i + take) - get(i) - get(i-1);
			if (!(mid & 1)) go += min(i>=take+1?x[i]-x[i-take-1]:INT_MAX,i+take+1<r?x[i+take+1]-x[i]:INT_MAX);
			if (go <= b) low = (ans = mid) + 1;
			else high = mid - 1;
		}
		ret = max(ret,ans);
	}
	return ret;
}

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