Submission #64679

#	Time	Username	Problem	Language	Result	Execution time	Memory
64679		Abelyan	Rice Hub (IOI11_ricehub)	C++17	100 / 100	38 ms	4312 KiB

ricehub

#include "ricehub.h"
#include <bits/stdc++.h>
typedef long long ll;
const int N=100050;
ll sum[N];
int x[N];
ll sm(int l, int r){
  return sum[r]-sum[l-1];
}
int besthub(int n, int sz, int D[], ll b)
{
	int i;
	for(i=1;i<=n;i++){
      	x[i]=D[i-1];
      	sum[i]=sum[i-1]+x[i];
    } 
	int r=n,l=1,mid,ans=1;
	while(r>=l)
	{
		mid=(l+r)/2;
		bool ok=0;
		for(i=mid;i<=n;i++)
		{
			int L=i-mid+1;
			int R=i;
			int M=(L+R)/2;
			ll cost=(ll)(M-L+1)*x[M]-sm(L,M);
			cost+=sm(M,R)-(ll)(R-M+1)*x[M];
			if(cost<=b){ ok=1;break;}
		}
		if(ok) ans=mid,l=mid+1;
		else r=mid-1;
	}
	return ans;
}

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