Submission #1216886

#	Time	Username	Problem	Language	Result	Execution time	Memory
1216886		giorgi123glm	Rice Hub (IOI11_ricehub)	C++20	68 / 100	15 ms	1864 KiB

ricehub

#include "ricehub.h"
#include <algorithm>
#include <cstdlib>
#include <iostream>
#include <set>
#include <vector>
using namespace std;

int besthub(int R, int L, int X[], long long B) {
	vector <int> v (R + 1);
	for (int i = 1; i <= R; i++)
		v[i] = X[i - 1];
	vector <long long> pref (R + 1);
	for (int i = 1; i <= R; i++)
		pref[i] = pref[i - 1] + v[i];

	int ans = 0;
	for (int i = 1; i <= R; i++) {
		// chooce rice hub
		
		int l = 0, r = R;
		while (l <= r) {
			int mid = (l + r) / 2;
			int x = mid / 2;
			int y = mid - x;

			if (i > (R + 1) / 2)
				swap (x, y);

			if (i - x - 1 < 0 || i + y > R) {
				r = mid - 1;
				continue;
			}
			
			long long prc = (
				x * v[i] - (pref[i - 1] - pref[i - x - 1]) +
				(pref[i + y] - pref[i]) - y * v[i]
			);
			if (prc <= B) {
				ans = max (ans, x + y + 1);
				l = mid + 1;
			} else {
				r = mid - 1;
			}
		}
	}

	return ans;
}

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