Submission #1294472

#	Time	Username	Problem	Language	Result	Execution time	Memory
1294472		m.zeeshanrashid	Rice Hub (IOI11_ricehub)	C++20	100 / 100	9 ms	2376 KiB

ricehub

#include "ricehub.h"
#include "bits/stdc++.h"
using namespace std;
#define ll long long

ll p[100005];


ll sum(int l,int r){
	return p[r]-p[l-1];
}


int besthub(int n, int idk, int X[], long long b){
	vector<ll>x(n+1,0);
	for(int i=1;i<=n;i++)
		x[i]=X[i-1];
	for(int i=1;i<=n;i++)
		p[i]=p[i-1]+x[i];
	int l=0,r=n+1;
	while(l+1<r){
		int m=(l+r)/2;
		ll mi=1e18;
		for(int e=m;e<=n;e++){
			int s=e-m+1;
			int me=(s+e)/2;
			ll val=x[me]*(me-s+1)-x[me]*(e-me+1);
			// cout<<e<<' '<<x[me]<<endl;
			// cout<<"fi "<<e<<' '<<val<<endl;
			val+=sum(me,e)-sum(s,me);
			// cout<<"se "<<e<<' '<<val<<endl;
			mi=min(mi,val);
		}
		// cout<<"mid "<<m<<' '<<mi<<endl;
		if(mi<=b) l=m;
		else r=m;
	}
	return l;
}

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