Submission #59274

#	Time	Username	Problem	Language	Result	Execution time	Memory
59274		TadijaSebez	Rice Hub (IOI11_ricehub)	C++11	100 / 100	35 ms	16616 KiB

ricehub

#include "ricehub.h"
#include <stdio.h>
#define ll long long
const int N=100050;
ll sum[N];
int x[N];
ll get(int l, int r){ return sum[r]-sum[l-1];}
int besthub(int n, int l, int X[], ll b)
{
	int i;
	for(i=1;i<=n;i++) x[i]=X[i-1],sum[i]=sum[i-1]+x[i];
	int top=n,bot=1,mid,ans=1;
	while(top>=bot)
	{
		mid=top+bot>>1;
		bool ok=0;
		for(i=mid;i<=n;i++)
		{
			int L=i-mid+1;
			int R=i;
			int M=L+R>>1;
			ll cost=(ll)(M-L+1)*x[M]-get(L,M);
			cost+=get(M,R)-(ll)(R-M+1)*x[M];
			if(cost<=b){ ok=1;break;}
		}
		if(ok) ans=mid,bot=mid+1;
		else top=mid-1;
	}
	return ans;
}
/*int X[N];
int main()
{
	int n,l,i;ll b;
	scanf("%i %i %lld",&n,&l,&b);
	for(i=0;i<n;i++) scanf("%i",&X[i]);
	printf("%i\n",besthub(n,l,X,b));
	return 0;
}*/

Compilation message (stderr)

ricehub.cpp: In function 'int besthub(int, int, int*, long long int)':
ricehub.cpp:15:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   mid=top+bot>>1;
       ~~~^~~~
ricehub.cpp:21:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    int M=L+R>>1;
          ~^~

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