Submission #641133

#	Time	Username	Problem	Language	Result	Execution time	Memory
641133		xiaossr	Rice Hub (IOI11_ricehub)	C++17	100 / 100	15 ms	2516 KiB

ricehub

// IOI 2011
// Day 1 Problem 3, Rice Hub

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

/*
* Idea: sliding window on range - 
*		if less dist take max?
*		median is the location of hub
*/

typedef long long ll;

ll psum[100005];

ll cst(int R, int l, int r)
{
	if (l == r) return 0;

	int mid = (l + r) / 2;
	if ((r - l) % 2) return psum[r] - psum[mid] - (psum[mid] - (l ? psum[l - 1] : 0));
	else return psum[r] - psum[mid] - (psum[mid - 1] - (l ? psum[l - 1] : 0));
}

// R: number of rice fields
// L: longest dist
// X: all the field's locations
// B: max number spent
// return best r - l + 1
int besthub(int R, int L, int X[], ll B)
{
	psum[0] = X[0];
	for (int i = 1; i < R; i++)
		psum[i] = psum[i - 1] + X[i];

	int l = 0, r = 0, ans = 1;
	while (r < R)
	{
		if (cst(R, l, r) <= B) ans = max(ans, r - l + 1);

		while (r + 1 < R && cst(R, l, r + 1) <= B)
		{
			++r;
			ans = max(ans, r - l + 1);
		}

		while (cst(R, l, r) > B)
			++l;
		++r;
	}

	return ans;
}

//int main()
//{
//	int arr[] = { 1, 4, 10, 11, 14 };
//	cout << besthub(5, 20, arr, 18);
//	return 0;
//}

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