#include "ricehub.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll cum[100005],tab[100005];
ll sum(int a,int b){
if(a>b)return 0;
return cum[b]-(a?cum[a-1]:0);
}
ll cost(int i,int j,int x){
ll idx=lower_bound(tab+i,tab+j+1,x)-tab;
ll nb_a=idx-i,nb_b=j-idx+1;
return nb_a*x-sum(i,idx-1)+sum(idx,j)-nb_b*x;
}
int besthub(int R, int L, int X[], long long B)
{
for (int i = 0; i < R; ++i)
{
tab[i]=X[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+ans; j < R; ++j)
{
//cerr<<i<<" "<<j<<" "<<i+(j-i)/2<<"\n";
if(cost(i,j,X[i+(j-i)/2])<=B)
ans=max(ans,j-i+1);
else break;
/*
ll x=sum(i,j)/(j-i+1);
if(cost(i,j,x)<=B)ans=max(ans,j-i+1);
else{
x=(sum(i,j)+(j-i))/(j-i+1);
if(cost(i,j,x)<=B)ans=max(ans,j-i+1);
}
*/
}
}
return ans;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
384 KB |
Output is correct |
| 2 |
Correct |
0 ms |
384 KB |
Output is correct |
| 3 |
Correct |
0 ms |
256 KB |
Output is correct |
| 4 |
Correct |
0 ms |
384 KB |
Output is correct |
| 5 |
Correct |
1 ms |
384 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
384 KB |
Output is correct |
| 2 |
Correct |
0 ms |
384 KB |
Output is correct |
| 3 |
Correct |
0 ms |
384 KB |
Output is correct |
| 4 |
Correct |
1 ms |
256 KB |
Output is correct |
| 5 |
Correct |
0 ms |
384 KB |
Output is correct |
| 6 |
Correct |
0 ms |
384 KB |
Output is correct |
| 7 |
Correct |
0 ms |
384 KB |
Output is correct |
| 8 |
Correct |
0 ms |
384 KB |
Output is correct |
| 9 |
Correct |
0 ms |
384 KB |
Output is correct |
| 10 |
Correct |
0 ms |
384 KB |
Output is correct |
| 11 |
Correct |
0 ms |
384 KB |
Output is correct |
| 12 |
Correct |
0 ms |
384 KB |
Output is correct |
| 13 |
Correct |
0 ms |
384 KB |
Output is correct |
| 14 |
Correct |
0 ms |
384 KB |
Output is correct |
| 15 |
Correct |
0 ms |
384 KB |
Output is correct |
| 16 |
Correct |
0 ms |
384 KB |
Output is correct |
| 17 |
Correct |
0 ms |
384 KB |
Output is correct |
| 18 |
Correct |
0 ms |
384 KB |
Output is correct |
| 19 |
Correct |
0 ms |
384 KB |
Output is correct |
| 20 |
Correct |
0 ms |
384 KB |
Output is correct |
| 21 |
Correct |
0 ms |
384 KB |
Output is correct |
| 22 |
Correct |
0 ms |
384 KB |
Output is correct |
| 23 |
Correct |
0 ms |
384 KB |
Output is correct |
| 24 |
Correct |
1 ms |
384 KB |
Output is correct |
| 25 |
Correct |
0 ms |
384 KB |
Output is correct |
| 26 |
Correct |
1 ms |
384 KB |
Output is correct |
| 27 |
Correct |
0 ms |
384 KB |
Output is correct |
| 28 |
Correct |
0 ms |
384 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
384 KB |
Output is correct |
| 2 |
Correct |
0 ms |
384 KB |
Output is correct |
| 3 |
Correct |
1 ms |
384 KB |
Output is correct |
| 4 |
Correct |
1 ms |
384 KB |
Output is correct |
| 5 |
Correct |
0 ms |
384 KB |
Output is correct |
| 6 |
Correct |
0 ms |
384 KB |
Output is correct |
| 7 |
Correct |
1 ms |
384 KB |
Output is correct |
| 8 |
Correct |
0 ms |
384 KB |
Output is correct |
| 9 |
Correct |
0 ms |
384 KB |
Output is correct |
| 10 |
Correct |
0 ms |
384 KB |
Output is correct |
| 11 |
Correct |
1 ms |
384 KB |
Output is correct |
| 12 |
Correct |
0 ms |
384 KB |
Output is correct |
| 13 |
Correct |
0 ms |
384 KB |
Output is correct |
| 14 |
Correct |
1 ms |
384 KB |
Output is correct |
| 15 |
Correct |
0 ms |
384 KB |
Output is correct |
| 16 |
Correct |
0 ms |
384 KB |
Output is correct |
| 17 |
Correct |
0 ms |
384 KB |
Output is correct |
| 18 |
Correct |
1 ms |
384 KB |
Output is correct |
| 19 |
Correct |
1 ms |
384 KB |
Output is correct |
| 20 |
Correct |
1 ms |
384 KB |
Output is correct |
| 21 |
Correct |
2 ms |
384 KB |
Output is correct |
| 22 |
Correct |
1 ms |
384 KB |
Output is correct |
| 23 |
Correct |
2 ms |
384 KB |
Output is correct |
| 24 |
Correct |
1 ms |
384 KB |
Output is correct |
| 25 |
Correct |
1 ms |
384 KB |
Output is correct |
| 26 |
Correct |
1 ms |
384 KB |
Output is correct |
| 27 |
Correct |
1 ms |
384 KB |
Output is correct |
| 28 |
Correct |
1 ms |
384 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
4 ms |
768 KB |
Output is correct |
| 2 |
Correct |
4 ms |
896 KB |
Output is correct |
| 3 |
Correct |
21 ms |
3328 KB |
Output is correct |
| 4 |
Correct |
24 ms |
3496 KB |
Output is correct |
| 5 |
Correct |
8 ms |
1664 KB |
Output is correct |
| 6 |
Correct |
9 ms |
1664 KB |
Output is correct |
| 7 |
Correct |
20 ms |
3072 KB |
Output is correct |
| 8 |
Correct |
20 ms |
3072 KB |
Output is correct |
| 9 |
Correct |
15 ms |
1664 KB |
Output is correct |
| 10 |
Correct |
9 ms |
1664 KB |
Output is correct |
| 11 |
Correct |
24 ms |
3320 KB |
Output is correct |
| 12 |
Correct |
24 ms |
3328 KB |
Output is correct |
| 13 |
Correct |
10 ms |
1664 KB |
Output is correct |
| 14 |
Correct |
11 ms |
1664 KB |
Output is correct |
| 15 |
Correct |
17 ms |
2560 KB |
Output is correct |
| 16 |
Correct |
20 ms |
2560 KB |
Output is correct |
| 17 |
Correct |
21 ms |
3064 KB |
Output is correct |
| 18 |
Correct |
25 ms |
3072 KB |
Output is correct |
| 19 |
Correct |
22 ms |
3200 KB |
Output is correct |
| 20 |
Correct |
21 ms |
3200 KB |
Output is correct |
