Submission #283608

#	Time	Username	Problem	Language	Result	Execution time	Memory
283608		TMJN	Rice Hub (IOI11_ricehub)	C++17	100 / 100	27 ms	2944 KiB

ricehub

#include "ricehub.h"
#include <bits/stdc++.h>
using namespace std;
int X[100000];
long long S[100001];
long long B;

bool calc(int l,int r,int p){
	int pp=lower_bound(X+l,X+r+1,p)-X;
	return ((long long)p*(pp-l)-(S[pp]-S[l])+S[r+1]-S[pp]-(long long)p*(r-pp+1))<=B;
}

int besthub(int R, int L, int x[], long long b){
	int l,r;
	l=0;
	r=R+1;
	B=b;
	for(int i=0;i<R;i++){
		X[i]=x[i];
	}
	for(int i=0;i<R;i++){
		S[i+1]=S[i]+X[i];
	}
	while(l+1!=r){
		int m=(l+r)/2;
		bool f=false;
		for(int i=0;i<=R-m;i++){
			int p=min(L,X[(i+i+m-1)/2]);
			f|=calc(i,i+m-1,p);
		}
		if(f){
			l=m;
		}
		else{
			r=m;
		}
	}
	return l;
}

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