#include <stdio.h>
#include <algorithm>
#define LL long long
using namespace std;
LL sum[111111];
int besthub(int R,int L,int X[],LL B){
sum[0]=X[0];
for(int i=1;i<R;i++) sum[i]=sum[i-1]+X[i];
int ans=0;
for(int i=0;i<R;i++){
int s=1,e=L,m;
while(s<=e){
m=(s+e)>>1;
int sidx=lower_bound(X,X+R,X[i]-m)-X;
int eidx=upper_bound(X,X+R,X[i]+m)-X-1;
if((sum[eidx]-sum[i])-(LL)X[i]*(eidx-i)+(LL)X[i]*(i-sidx)-((!i?0:sum[i-1])-(!sidx?0:sum[sidx-1]))<=B) s=m+1;
else e=m-1;
}
int sidx=lower_bound(X,X+R,X[i]-e)-X;
int eidx=upper_bound(X,X+R,X[i]+e)-X-1;
int sidx2=lower_bound(X,X+R,X[i]-s)-X;
int eidx2=upper_bound(X,X+R,X[i]+s)-X-1;
LL res=(sum[eidx]-sum[i])-(LL)X[i]*(eidx-i)+(LL)X[i]*(i-sidx)-((!i?0:sum[i-1])-(!sidx?0:sum[sidx-1]));
if(sidx!=sidx2) ans=max((LL)ans,eidx-sidx+1+min((LL)eidx2-eidx+sidx-sidx2,(B-res)/(X[i]-X[sidx2])));
else if(eidx!=eidx2) ans=max((LL)ans,eidx-sidx+1+min((LL)eidx2-eidx+sidx-sidx2,(B-res)/(X[eidx2]-X[i])));
else ans=max(ans,eidx-sidx+1);
}
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
1 ms |
376 KB |
Output is correct |
| 3 |
Correct |
1 ms |
256 KB |
Output is correct |
| 4 |
Correct |
2 ms |
348 KB |
Output is correct |
| 5 |
Correct |
2 ms |
256 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
256 KB |
Output is correct |
| 2 |
Correct |
2 ms |
292 KB |
Output is correct |
| 3 |
Correct |
2 ms |
376 KB |
Output is correct |
| 4 |
Correct |
2 ms |
256 KB |
Output is correct |
| 5 |
Correct |
2 ms |
256 KB |
Output is correct |
| 6 |
Correct |
2 ms |
252 KB |
Output is correct |
| 7 |
Correct |
2 ms |
256 KB |
Output is correct |
| 8 |
Correct |
2 ms |
256 KB |
Output is correct |
| 9 |
Correct |
2 ms |
256 KB |
Output is correct |
| 10 |
Correct |
2 ms |
376 KB |
Output is correct |
| 11 |
Correct |
2 ms |
256 KB |
Output is correct |
| 12 |
Correct |
2 ms |
256 KB |
Output is correct |
| 13 |
Correct |
2 ms |
256 KB |
Output is correct |
| 14 |
Correct |
2 ms |
256 KB |
Output is correct |
| 15 |
Correct |
2 ms |
256 KB |
Output is correct |
| 16 |
Correct |
2 ms |
256 KB |
Output is correct |
| 17 |
Correct |
2 ms |
256 KB |
Output is correct |
| 18 |
Correct |
2 ms |
252 KB |
Output is correct |
| 19 |
Correct |
2 ms |
256 KB |
Output is correct |
| 20 |
Correct |
2 ms |
252 KB |
Output is correct |
| 21 |
Correct |
2 ms |
376 KB |
Output is correct |
| 22 |
Correct |
2 ms |
376 KB |
Output is correct |
| 23 |
Correct |
2 ms |
256 KB |
Output is correct |
| 24 |
Correct |
2 ms |
380 KB |
Output is correct |
| 25 |
Correct |
2 ms |
376 KB |
Output is correct |
| 26 |
Correct |
2 ms |
376 KB |
Output is correct |
| 27 |
Correct |
2 ms |
376 KB |
Output is correct |
| 28 |
Correct |
2 ms |
256 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
252 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Correct |
2 ms |
256 KB |
Output is correct |
| 4 |
Correct |
2 ms |
256 KB |
Output is correct |
| 5 |
Correct |
2 ms |
256 KB |
Output is correct |
| 6 |
Correct |
2 ms |
256 KB |
Output is correct |
| 7 |
Correct |
2 ms |
256 KB |
Output is correct |
| 8 |
Correct |
2 ms |
256 KB |
Output is correct |
| 9 |
Correct |
2 ms |
252 KB |
Output is correct |
| 10 |
Correct |
2 ms |
376 KB |
Output is correct |
| 11 |
Correct |
2 ms |
256 KB |
Output is correct |
| 12 |
Correct |
2 ms |
256 KB |
Output is correct |
| 13 |
Correct |
2 ms |
256 KB |
Output is correct |
| 14 |
Correct |
2 ms |
256 KB |
Output is correct |
| 15 |
Correct |
2 ms |
376 KB |
Output is correct |
| 16 |
Correct |
2 ms |
256 KB |
Output is correct |
| 17 |
Correct |
2 ms |
256 KB |
Output is correct |
| 18 |
Correct |
2 ms |
256 KB |
Output is correct |
| 19 |
Correct |
2 ms |
256 KB |
Output is correct |
| 20 |
Correct |
3 ms |
256 KB |
Output is correct |
| 21 |
Correct |
4 ms |
376 KB |
Output is correct |
| 22 |
Correct |
4 ms |
376 KB |
Output is correct |
| 23 |
Correct |
5 ms |
376 KB |
Output is correct |
| 24 |
Correct |
19 ms |
376 KB |
Output is correct |
| 25 |
Correct |
7 ms |
376 KB |
Output is correct |
| 26 |
Correct |
8 ms |
376 KB |
Output is correct |
| 27 |
Correct |
9 ms |
376 KB |
Output is correct |
| 28 |
Correct |
10 ms |
376 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
41 ms |
632 KB |
Output is correct |
| 2 |
Correct |
43 ms |
632 KB |
Output is correct |
| 3 |
Correct |
156 ms |
2680 KB |
Output is correct |
| 4 |
Correct |
220 ms |
2624 KB |
Output is correct |
| 5 |
Correct |
53 ms |
1272 KB |
Output is correct |
| 6 |
Correct |
54 ms |
1192 KB |
Output is correct |
| 7 |
Correct |
105 ms |
2332 KB |
Output is correct |
| 8 |
Correct |
116 ms |
2296 KB |
Output is correct |
| 9 |
Correct |
60 ms |
1144 KB |
Output is correct |
| 10 |
Correct |
61 ms |
1144 KB |
Output is correct |
| 11 |
Correct |
152 ms |
2640 KB |
Output is correct |
| 12 |
Correct |
207 ms |
2552 KB |
Output is correct |
| 13 |
Correct |
110 ms |
1272 KB |
Output is correct |
| 14 |
Correct |
112 ms |
1328 KB |
Output is correct |
| 15 |
Correct |
115 ms |
2044 KB |
Output is correct |
| 16 |
Correct |
154 ms |
2040 KB |
Output is correct |
| 17 |
Correct |
136 ms |
2296 KB |
Output is correct |
| 18 |
Correct |
186 ms |
2400 KB |
Output is correct |
| 19 |
Correct |
145 ms |
2552 KB |
Output is correct |
| 20 |
Correct |
199 ms |
2552 KB |
Output is correct |
