Submission #1264279

#	Time	Username	Problem	Language	Result	Execution time	Memory
1264279		liangjeremy	Rice Hub (IOI11_ricehub)	C++20	100 / 100	155 ms	7000 KiB

ricehub

#include "ricehub.h"
#include<bits/stdc++.h>
#define fi first
#define se second
//#define int long long
using namespace std;
using db=double;
using ll=int64_t;
using sll=__int128;
using lb=long double;

int besthub(int n, int m, int a[], long long mx){
#define int long long
	vector<int>v(n+1); vector<int>prefix(n+1); 
	for(int i=0; i<n; i++){
		v[i+1]=a[i]; prefix[i+1]=v[i+1]+prefix[i];
	}
	int ans=0; unordered_map<int,int>mp; 
	for(int i=1; i<=n; i++)mp[v[i]]++; 
	auto check=[&](int mid, int idx){
		long long tot=0; 
		int lidx=lower_bound(v.begin()+1,v.end(),v[idx]-mid)-v.begin();
		int ridx=upper_bound(v.begin()+1,v.end(),v[idx]+mid)-v.begin()-1; 
		if(lidx<idx){
			tot+=v[idx]*(idx-lidx)-(prefix[idx-1]-prefix[lidx-1]); 
		}
		if(ridx>idx){
			tot+=(prefix[ridx]-prefix[idx])-v[idx]*(ridx-idx); 
		}
		return tot; 
	};
	for(int i=1; i<=n; i++){
		int left=0; int right=v[n]-v[1]; int amt=mx; 
		while(left<right){
			int mid=(left+right+1)>>1; 
			if(check(mid,i)<=mx)left=mid; else right=mid-1; 
		}
		int lidx=lower_bound(v.begin()+1,v.end(),v[i]-left)-v.begin();		
		int ridx=upper_bound(v.begin()+1,v.end(),v[i]+left)-v.begin()-1; 
		if(lidx<i){
			amt-=v[i]*(i-lidx)-(prefix[i-1]-prefix[lidx-1]); 
		}
		if(ridx>i){
			amt-=(prefix[ridx]-prefix[i])-v[i]*(ridx-i); 
		}
		int l=1e18; int r=1e18; int cur=ridx-lidx+1; 
		if(lidx-1>0)l=abs(v[i]-v[lidx-1]);
		if(ridx+1<=n)r=abs(v[i]-v[ridx+1]);  
		if(min(l,r)==1e18){
			ans=max(ans,cur); continue; 
		}
		if(l<r){
			cur+=min((int)(amt/l),mp[v[lidx-1]]); 
		}else if(r<l){
			cur+=min((int)(amt/r),mp[v[ridx+1]]); 
		}else if(r==l){
			cur+=min((int)(amt/r),mp[v[ridx+1]]+mp[v[lidx-1]]); 
		}
		ans=max(ans,cur); 
	}
#undef int 
	return ans; 
}

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