Submission #518807

#	Time	Username	Problem	Language	Result	Execution time	Memory
518807		sliviu	Rice Hub (IOI11_ricehub)	C++17	100 / 100	12 ms	2376 KiB

ricehub

#include <bits/stdc++.h>
#include "ricehub.h"

using namespace std;

int besthub(int n, int L, int a[], long long cmax) {
	vector<long long> s(n + 1);
	for (int i = 1; i <= n; ++i)
		s[i] = s[i - 1] + a[i - 1];
	int ans = 0;
	for (int i = 1, j = 1; i <= n; ++i) {
		auto cost = [&](int l, int r) {
			int m = (l + r) / 2;
			return 1LL * (m - l) * a[m - 1] - (s[m - 1] - s[i - 1]) + s[r] - s[m] - 1LL * (r - m) * a[m - 1];
		};
		while (j + 1 <= n && cost(i, j + 1) <= cmax)
			++j;
		ans = max(ans, j - i + 1);
	}
	return ans;
}

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