Submission #285733

#	Time	Username	Problem	Language	Result	Execution time	Memory
285733		peijar	Rice Hub (IOI11_ricehub)	C++17	100 / 100	24 ms	3328 KiB

ricehub

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

#define SZ(v) ((int)(v).size())
using ll = long long;

const int MAXN = 1e5+1;

ll prefixSum[MAXN];
ll cntFields, maxCor, budget;
ll cor[MAXN];

ll getCost(int l, int r)
{
	int mid = (l+r)/2;
	ll cost = (2*mid-l-r) * cor[mid] + prefixSum[r+1] + prefixSum[l] - prefixSum[mid] - prefixSum[mid+1];
	return cost;
}

bool can(int want)
{
	for (int i(0); i + want <= cntFields; ++i)
		if (getCost(i, i+want-1) <= budget)
			return true;
	return false;
}

int besthub(int c, int m, int co[], ll b)
{
	budget = b;
	cntFields = c;
	maxCor = m;
	for (int i(0); i < cntFields; ++i)
		cor[i] = co[i];
	for (int i(0); i < cntFields; ++i)
		prefixSum[i+1] = prefixSum[i] + cor[i];

	int lo(0), up(cntFields);
	while (lo < up)
	{
		int mid = (lo+up+1)/2;
		if (can(mid)) lo = mid;
		else up = mid-1;
	}
	return lo;
}

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