Submission #364905

#	Time	Username	Problem	Language	Result	Execution time	Memory
364905		hoaphat1	Rice Hub (IOI11_ricehub)	C++17	100 / 100	21 ms	2668 KiB

ricehub

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

int besthub(int n, int lim, int a[], long long b) {
	int l = 1, r = n;
	vector<long long> t(n);
	for (int i = 0; i < n; i++) {
		t[i] = a[i];
		if (i) t[i] += t[i-1];
	}
	auto getv = [&](int l, int r) {
		if (!l) return t[r];
		return t[r] - t[l-1];
	};
	auto test = [&](int num) {
		for (int i = 0; i + num <= n; i++) {
			auto get = [&](int n) {
				return -getv(i, i + n - 1) + getv(i + n, i + num - 1) - 1ll * a[i + n - 1] * (num - n - n);
			};
			if (min(get(num / 2), get((num + 1) / 2)) <= b) return true;
		}
		return false;
	};
	while (l <= r) {
		int mid = l + r >> 1;
		if (test(mid)) l = mid + 1;
		else r = mid - 1;
	}
	return r;
}

Compilation message (stderr)

ricehub.cpp: In function 'int besthub(int, int, int*, long long int)':
ricehub.cpp:26:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   26 |   int mid = l + r >> 1;
      |             ~~^~~

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