Submission #91243

#	Time	Username	Problem	Language	Result	Execution time	Memory
91243		arman_ferdous	Rice Hub (IOI11_ricehub)	C++17	83 / 100	35 ms	2560 KiB

ricehub

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

typedef long long ll;
const int N = 1e5+10;

int n; ll arr[N], sum[N];

ll get(ll l, ll r, ll M) {
	ll ret = 0;
	if(arr[r] <= M) return (r - l + 1) * M - sum[r] + sum[l-1];
	if(M <= arr[l]) return sum[r] - sum[l-1] - (r - l + 1) * M;
	int p = lower_bound(arr,arr+n,M) - arr;
	return M * (p - l) - sum[p-1] + sum[l-1] + sum[r] - sum[p-1] - M * (r - p + 1);
}

int besthub(int R, int L, int X[], ll B) {
	n = R;
	for(int i = 1; i <= n; i++) arr[i] = X[i-1];
	for(int i = 1; i <= n; i++) sum[i] = sum[i-1] + arr[i];

	int lo = 1, hi = n, ans = 1;
	while(lo <= hi) {
		int mid = (lo + hi) >> 1;
		int can = 0;
		for(int i = 1; i + mid - 1 <= n; i++) {
			int med;
			if(mid & 1) med = arr[i + mid/2];
			else med = (arr[i + mid/2] + arr[i + mid/2 + 1]) / 2;
			if(get(i, i + mid - 1, med) <= B) { can = 1; break; }
		} 
		if(can) ans = mid, lo = mid + 1;
		else hi = mid - 1;
	} return ans;
}

Compilation message (stderr)

ricehub.cpp: In function 'll get(ll, ll, ll)':
ricehub.cpp:11:5: warning: unused variable 'ret' [-Wunused-variable]
  ll ret = 0;
     ^~~

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