oj.uz

Submission #112973

# Submission time Handle Problem Language Result Execution time Memory
112973 2019-05-22T22:41:06 Z andremfq Rice Hub (IOI11_ricehub) C++17
68 / 100
 19 ms 4144 KB 
#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=1;i<=r;i++)	sp1[i]=sp1[i-1]+x[i];
	
	for(int i=r;i>0;i--)	sp2[i]=sp2[i+1]+(l-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]));
		
		int op2=sp2[ini]-sp2[m]-((m-ini)*(l-x[m]));
		
		debug("op1 = %d  op2 = %d  ini = %d  fim = %d\n",op1,op2,ini,fim);
		
		if(op1+op2<=b)	resp=max(resp,fim-ini+1),	fim++;
		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

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

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 2 ms 384 KB Output is correct
13 Correct 2 ms 384 KB Output is correct
14 Correct 2 ms 384 KB Output is correct
15 Correct 2 ms 384 KB Output is correct
16 Correct 2 ms 384 KB Output is correct
17 Correct 2 ms 384 KB Output is correct
18 Correct 2 ms 384 KB Output is correct
19 Correct 2 ms 384 KB Output is correct
20 Correct 2 ms 384 KB Output is correct
21 Correct 2 ms 384 KB Output is correct
22 Correct 2 ms 356 KB Output is correct
23 Correct 2 ms 384 KB Output is correct
24 Correct 2 ms 384 KB Output is correct
25 Correct 2 ms 384 KB Output is correct
26 Correct 2 ms 384 KB Output is correct
27 Correct 2 ms 384 KB Output is correct
28 Correct 2 ms 384 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 2 ms 384 KB Output is correct
13 Correct 2 ms 384 KB Output is correct
14 Correct 2 ms 384 KB Output is correct
15 Correct 2 ms 384 KB Output is correct
16 Correct 2 ms 384 KB Output is correct
17 Correct 2 ms 384 KB Output is correct
18 Correct 2 ms 384 KB Output is correct
19 Correct 2 ms 384 KB Output is correct
20 Correct 2 ms 384 KB Output is correct
21 Correct 2 ms 512 KB Output is correct
22 Correct 2 ms 512 KB Output is correct
23 Correct 2 ms 512 KB Output is correct
24 Correct 2 ms 412 KB Output is correct
25 Correct 3 ms 512 KB Output is correct
26 Correct 3 ms 512 KB Output is correct
27 Correct 3 ms 512 KB Output is correct
28 Correct 3 ms 512 KB Output is correct

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 896 KB Output is correct
2 Correct 5 ms 1024 KB Output is correct
3 Correct 18 ms 4096 KB Output is correct
4 Incorrect 19 ms 4144 KB Output isn't correct
5 Halted 0 ms 0 KB -