oj.uz

Submission #641132

# Submission time Handle Problem Language Result Execution time Memory
641132 2022-09-16T04:29:57 Z xiaossr Rice Hub (IOI11_ricehub) C++17
0 / 100
 2 ms 468 KB 
// 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 % 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 (l < r && cst(R, l, r) > B)
		{
			++l;
		}
		++r;
	}

	return ans;
}

//int main()
//{
//	int arr[] = { 1, 2, 10, 12, 14 };
//	cout << besthub(5, 20, arr, 6);
//	return 0;
//}

Subtask #1
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 0 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Incorrect 0 ms 212 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 468 KB Output isn't correct
2 Halted 0 ms 0 KB -