Submission #655269

#	Time	Username	Problem	Language	Result	Execution time	Memory
655269		happypotato	Rice Hub (IOI11_ricehub)	C++17	100 / 100	17 ms	3256 KiB

ricehub

#include "ricehub.h"
using namespace std;
#define ll long long
const int mxN = 1e5 + 1;
ll int a[mxN], ps[mxN];
ll int budget;
int n;
bool test(int tar) {
	for (int i = (tar + 1) / 2; i <= n - tar / 2; i++) {
		ll int cur = 0;
		if (tar % 2 == 1) {
			cur += (a[i] * (tar / 2)) - (ps[i - 1] - ps[i - 1 - tar / 2]);
			cur += (ps[i + tar / 2] - ps[i]) - (a[i] * (tar / 2));
		} else {
			cur += (a[i] * (tar / 2)) - (ps[i] - ps[i - tar / 2]);
			cur += (ps[i + tar / 2] - ps[i]) - (a[i] * (tar / 2));
		}
		if (cur <= budget) return true;
	}
	return false;
}
int besthub(int R, int L, int X[], long long B) {
	n = R;
	for (int i = 1; i <= n; i++) {
		a[i] = X[i - 1];
		ps[i] = ps[i - 1] + a[i];
	}
	budget = B;
	int lb = 1, rb = n;
	while (lb < rb) {
		int mid = (lb + rb + 1) >> 1;
		if (test(mid)) lb = mid;
		else rb = mid - 1;
	}
	return lb;
}

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