Submission #1269075

#	Time	Username	Problem	Language	Result	Execution time	Memory
1269075		WH8	Rice Hub (IOI11_ricehub)	C++20	100 / 100	145 ms	3296 KiB

ricehub

#include "ricehub.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int besthub(int R, int L, int X[], ll B)
{
	vector<ll> v;
	for(int i=0;i<R;i++){
		v.push_back(X[i]);
	}
	vector<ll> sfx(R), pfx(R);
	ll ans=1;
	sfx[R-1]=L-v[R-1];
	pfx[0]=v[0];
	for(int i=1;i<R;i++)pfx[i]=pfx[i-1]+v[i];
	for(int i=R-1;i>=0;i--)sfx[i]=sfx[i+1]+(L-v[i]);
	for(int i=0;i<R;i++){
		int l=0,r=L+1;
		while(r-l>1){
			ll d=(l+r)/2;
			ll lb=lower_bound(v.begin(),v.end(),v[i]-d)-v.begin();
			ll ub=upper_bound(v.begin(),v.end(),v[i]+d)-v.begin();
			ll bel=sfx[lb] - sfx[i] - (i-lb)*(L-v[i]);
			ll abv=pfx[ub-1]-pfx[i] - (ub-i-1)*v[i];
			//~ printf("d is %lld, lb %lld ub %lld bel %lld abv %lld\n", d,lb,ub,bel,abv);
			if(bel + abv > B){
				r=d;
			}
			else {
				l=d;
			}
		}
		ll d=l;
		ll lb=lower_bound(v.begin(),v.end(),v[i]-d)-v.begin();
		ll ub=upper_bound(v.begin(),v.end(),v[i]+d)-v.begin();
		ll bel=sfx[lb] - sfx[i] - (i-lb)*(L-v[i]);
		ll abv=pfx[ub-1]-pfx[i] - (ub-i-1)*v[i];
		assert(bel + abv <= B);
		ll left=B-bel-abv;
		ll nxt=min((lb == 0? 1e16 : v[i]-v[lb-1]), (ub == R ? 1e16:v[ub]-v[i]));
		ll add=left/nxt;
		ll cand=ub-lb+add;
		ans=max(ans,cand);
	}
	return ans;
}

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