제출 #259452

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
259452		amiratou	Rice Hub (IOI11_ricehub)	C++14	17 / 100	1094 ms	640 KiB

ricehub

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

int cum[100005];
int sum(int a,int b){
	if(a>b)return 0;
	return cum[b]-(a?cum[a-1]:0);
}

int besthub(int R, int L, int X[], long long B)
{
	for (int i = 0; i < R; ++i)
	{
		cum[i]=X[i];
		if(i)cum[i]+=cum[i-1];
	}
	int ans=1;
	for (int i = 0; i < R; ++i)
	{
		for (int j = i+1; j < R; ++j)
		{
			ll x=sum(i,j)/(j-i+1);
			ll idx=lower_bound(X+i,X+j,x)-X;
			ll nb_a=idx-i,nb_b=j-idx+1;
			ll cost=nb_a*x-sum(i,idx-1)+sum(idx,j)-nb_b*x;
			if(cost<=B)ans=max(ans,j-i+1);
			else{
				x=(sum(i,j)+(j-i))/(j-i+1);
				idx=lower_bound(X+i,X+j,x)-X;
				nb_a=idx-i,nb_b=j-idx+1;
				cost=nb_a*x-sum(i,idx-1)+sum(idx,j)-nb_b*x;
				if(cost<=B)ans=max(ans,j-i+1);
			}
		}
	}
	return ans;
}

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