Submission #307991

#	Time	Username	Problem	Language	Result	Execution time	Memory
307991		tengiz05	Rice Hub (IOI11_ricehub)	C++17	0 / 100	4 ms	512 KiB

ricehub

#include "ricehub.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+5;
int a[N], n;
long long b;
bool check(int cnt){
	//two pointers?
	int l=0, r=cnt-1;
	long long suml = 0, sumr = 0;
	long long m = a[cnt/2];
	for(int i=0; i<cnt/2; i++)suml += m-a[i];
	for(int i=cnt/2;i<cnt;i++)sumr += a[i]-m;
	
	bool flag = false;
	while(true){
	//	cout << suml << ' ' << sumr << '\n';
		if(b >= suml + sumr)flag = true;
		
		l++, r++;
		int median = l + cnt/2;
		if(r >= n)break;
		suml -= a[median-1]-a[l-1];
		suml += (cnt/2)*(a[median]-a[median-1]);
		sumr -= (cnt/2)*(a[median]-a[median-1]);
		sumr += a[r]-a[median];
	}
	return flag;
}
int besthub(int R, int L, int X[], long long B){
	n = R;
	b = B;
	for(int i=0;i<n;i++)a[i] = X[i];
	int l=0, r=R+1;
//	cout << check(3) << '\n';
	while(l+1<r){
		int mid = (l+r)/2;
		if(check(mid)){
			l = mid;
		}else {
			r = mid;
		}
	}
	return l;
}

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