Submission #384277

#	Time	Username	Problem	Language	Result	Execution time	Memory
384277		Drew_	Rice Hub (IOI11_ricehub)	C++14	100 / 100	98 ms	3308 KiB

ricehub

#include "ricehub.h"
#include <iostream>
using namespace std;

#define ll long long
#define int ll

const int MAX = 1e5 + 7;

int n;
ll ar[MAX];
ll pfx[MAX];
ll budget;

int solve(int hub) //place a hub in ar[hub], calculate maximum amount of rice
{
	int l1 = 1, r1 = hub;
	while (l1 < r1)
	{
		int mid1 = (l1 + r1) / 2;
		ll cost1 = (hub - mid1) * ar[hub] - (pfx[hub-1] - pfx[mid1 - 1]);
		ll rt_cost = (pfx[n] - pfx[hub-1]) - (n - hub + 1) * ar[hub];

		if (cost1 > budget) l1 = mid1 + 1;
		else if (cost1 + rt_cost <= budget) r1 = mid1;
		else
		{
			int l2 = hub, r2 = n;
			while (l2 < r2)
			{
				int mid2 = (l2 + r2 + 1) / 2;
				ll cost2 = (pfx[mid2] - pfx[hub-1]) - (mid2 - hub + 1) * ar[hub];

				if (cost1 + cost2 <= budget) l2 = mid2;
				else r2 = mid2 - 1;
			}

			if (ar[l2+1] - ar[hub] < ar[hub] - ar[mid1]) l1 = mid1 + 1;
			else r1 = mid1;
		}
	}

	ll cost1 = (hub - l1) * ar[hub] - (pfx[hub-1] - pfx[l1 - 1]);

	int l2 = hub, r2 = n;
	while (l2 < r2)
	{
		int mid2 = (l2 + r2 + 1) / 2;
		ll cost2 = (pfx[mid2] - pfx[hub-1]) - (mid2 - hub + 1) * ar[hub];

		if (cost1 + cost2 <= budget) l2 = mid2;
		else r2 = mid2 - 1;
	}

	return l2 - l1 + 1;
}

int32_t besthub(int32_t R, int32_t L, int32_t X[], long long B)
{
	n = R;
	budget = B;

	for (int i = 1; i <= R; ++i)
	{
		ar[i] = X[i-1];
		pfx[i] = pfx[i-1] + X[i-1];
	}


	int res = 0;
	for (int i = 1; i <= R; ++i)
	{
		//cerr << i << ": " << solve(i) << '\n';
		res = max(res, solve(i));
	}
	return res;
}

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