Submission #111650

#	Time	Username	Problem	Language	Result	Execution time	Memory
111650		andremfq	Rice Hub (IOI11_ricehub)	C++17	0 / 100	5 ms	896 KiB

ricehub

#include<bits/stdc++.h>
#include"ricehub.h"
#define debug(args...)	fprintf(stderr,args)
using namespace std;
const int MAXR=100010;

int R,L,X[MAXR];
long long int sp1[MAXR],sp2[MAXR],x[MAXR];
long long int B;
int resp;

int besthub(int r,int l,int v[],long long int b)
{	
	sort(v,v+r);
	for(int i=0;i<r;i++)	x[i+1]=v[i];
	
	for(int i=2;i<=r;i++)	sp1[i]=sp1[i-1]+x[i];
	
	for(int i=r-1;i>0;i--)	sp2[i]=sp2[i+1]+x[i];
	
	int ini=1,	fim=1;
	while(fim<r)
	{
		if(ini>fim)		fim++;
		
		int m=(ini+fim)/2;
		
		int op1=sp1[fim]-sp1[m]-((fim-m)*(x[m]-x[0]));
		
		int op2=sp1[m-1]-sp1[ini-1]-((m-1-ini)*(x[r]-x[m]));
		
		if(op1+op2<=b)	fim++,	resp=max(resp,fim-ini+1);
		else ini++;
	}
	
	return resp;
}
/*
int main ()
{	
	scanf("%d %d",&R,&L);
	
	for(int i=0;i<R;i++)	scanf("%d",&X[i]);
	
	scanf("%lld",&B);
	
	int RESP=besthub(R,L,X,B);
	
	printf("%lld\n",RESP);
}

/*
5 20 
1 2 10 12 14
6
*/

Compilation message (stderr)

ricehub.cpp:52:1: warning: "/*" within comment [-Wcomment]
 /*

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