Submission #235873

#	Time	Username	Problem	Language	Result	Execution time	Memory
235873		Dilshod_Imomov	Rice Hub (IOI11_ricehub)	C++17	100 / 100	27 ms	2176 KiB

ricehub

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

long long ps[100100];

bool can( int k, LL b, int n, int a[] ) {
	int j = k - 1;
	for ( int i = 0; j < n; j++ ) {
		int x = a[(i + j) / 2], m = (i + j) / 2;
		LL sum = ps[m - 1];
		if ( i ) {
			sum -= ps[i - 1];
		}
		sum = (m - i) * x - sum;
		LL sum1 = ps[j] - ps[m];
		sum1 -= x * (j - m);
		LL cnt = sum + sum1;
		if ( cnt <= b ) {
			return 1;
		}
		i++;
	}
	return 0;
}

int besthub(int n, int mx, int a[], long long b)
{
	
	for ( int i = 0; i < n; i++ ) {
		ps[i] = a[i];
		if ( i ) {
			ps[i] += ps[i - 1];
		}
	}

	int l = 0, r = n, m, ans = 1;
	while ( l <= r ) {
		m = (l + r) / 2;
		if ( can( m, b, n, a ) ) {
			ans = m;
			l = m + 1;
		}
		else {
			r = m - 1;
		}
	}
	return ans;
}

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