Submission #157770

#	Time	Username	Problem	Language	Result	Execution time	Memory
157770		keta_tsimakuridze	Rice Hub (IOI11_ricehub)	C++14	100 / 100	29 ms	3352 KiB

ricehub

#include<bits/stdc++.h>
using namespace std;
long long k,prefsum[100005],mid,midin,L,R,pas,curprice,a[100005];
long long besthub(int r,int l,int x[],long long b ){
	for(k=1;k<=r;k++){
		a[k]=x[k-1];
		prefsum[k]=prefsum[k-1]+a[k];
	}
	
       for(k=1;k<=r;k++){
       	
       	
       	L=k; R=r;
       	while(L<=R){
       		mid=(L+R+1)/2;
       		midin=(mid+k)/2;
       	curprice=prefsum[mid]-prefsum[midin]-(mid-midin)*a[midin]
       	+ (midin-k+1)*a[midin]-prefsum[midin]+prefsum[k-1];
       //	cout<<k<<" "<<mid<<" = "<<curprice<<endl;
       	if(curprice<=b){
       		L=mid+1; pas=max(pas,mid-k+1);
		}
		else R=mid-1;
		
		}
	}
	return pas;
}

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