#include "ricehub.h"
#include <stdio.h>
#define ll long long
const int N=100050;
ll sum[N];
int x[N];
ll get(int l, int r){ return sum[r]-sum[l-1];}
int besthub(int n, int l, int X[], ll b)
{
int i;
for(i=1;i<=n;i++) x[i]=X[i-1],sum[i]=sum[i-1]+x[i];
int top=n,bot=1,mid,ans=1;
while(top>=bot)
{
mid=top+bot>>1;
bool ok=0;
for(i=mid;i<=n;i++)
{
int L=i-mid+1;
int R=i;
int M=L+R>>1;
ll cost=(ll)(M-L+1)*x[M]-get(L,M);
cost+=get(M,R)-(ll)(R-M+1)*x[M];
if(cost<=b){ ok=1;break;}
}
if(ok) ans=mid,bot=mid+1;
else top=mid-1;
}
return ans;
}
/*int X[N];
int main()
{
int n,l,i;ll b;
scanf("%i %i %lld",&n,&l,&b);
for(i=0;i<n;i++) scanf("%i",&X[i]);
printf("%i\n",besthub(n,l,X,b));
return 0;
}*/
Compilation message
ricehub.cpp: In function 'int besthub(int, int, int*, long long int)':
ricehub.cpp:15:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
mid=top+bot>>1;
~~~^~~~
ricehub.cpp:21:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int M=L+R>>1;
~^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
608 KB |
Output is correct |
| 3 |
Correct |
2 ms |
608 KB |
Output is correct |
| 4 |
Correct |
2 ms |
648 KB |
Output is correct |
| 5 |
Correct |
2 ms |
648 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
832 KB |
Output is correct |
| 2 |
Correct |
2 ms |
832 KB |
Output is correct |
| 3 |
Correct |
2 ms |
832 KB |
Output is correct |
| 4 |
Correct |
2 ms |
832 KB |
Output is correct |
| 5 |
Correct |
3 ms |
1004 KB |
Output is correct |
| 6 |
Correct |
2 ms |
1004 KB |
Output is correct |
| 7 |
Correct |
2 ms |
1004 KB |
Output is correct |
| 8 |
Correct |
2 ms |
1004 KB |
Output is correct |
| 9 |
Correct |
3 ms |
1004 KB |
Output is correct |
| 10 |
Correct |
3 ms |
1004 KB |
Output is correct |
| 11 |
Correct |
3 ms |
1004 KB |
Output is correct |
| 12 |
Correct |
2 ms |
1004 KB |
Output is correct |
| 13 |
Correct |
2 ms |
1004 KB |
Output is correct |
| 14 |
Correct |
2 ms |
1004 KB |
Output is correct |
| 15 |
Correct |
3 ms |
1004 KB |
Output is correct |
| 16 |
Correct |
3 ms |
1004 KB |
Output is correct |
| 17 |
Correct |
2 ms |
1004 KB |
Output is correct |
| 18 |
Correct |
2 ms |
1004 KB |
Output is correct |
| 19 |
Correct |
2 ms |
1004 KB |
Output is correct |
| 20 |
Correct |
2 ms |
1004 KB |
Output is correct |
| 21 |
Correct |
2 ms |
1004 KB |
Output is correct |
| 22 |
Correct |
3 ms |
1004 KB |
Output is correct |
| 23 |
Correct |
4 ms |
1056 KB |
Output is correct |
| 24 |
Correct |
3 ms |
1056 KB |
Output is correct |
| 25 |
Correct |
3 ms |
1060 KB |
Output is correct |
| 26 |
Correct |
3 ms |
1084 KB |
Output is correct |
| 27 |
Correct |
3 ms |
1088 KB |
Output is correct |
| 28 |
Correct |
3 ms |
1088 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
1088 KB |
Output is correct |
| 2 |
Correct |
3 ms |
1088 KB |
Output is correct |
| 3 |
Correct |
3 ms |
1104 KB |
Output is correct |
| 4 |
Correct |
3 ms |
1112 KB |
Output is correct |
| 5 |
Correct |
3 ms |
1112 KB |
Output is correct |
| 6 |
Correct |
2 ms |
1112 KB |
Output is correct |
| 7 |
Correct |
2 ms |
1148 KB |
Output is correct |
| 8 |
Correct |
3 ms |
1168 KB |
Output is correct |
| 9 |
Correct |
3 ms |
1192 KB |
Output is correct |
| 10 |
Correct |
3 ms |
1192 KB |
Output is correct |
| 11 |
Correct |
2 ms |
1200 KB |
Output is correct |
| 12 |
Correct |
3 ms |
1224 KB |
Output is correct |
| 13 |
Correct |
3 ms |
1364 KB |
Output is correct |
| 14 |
Correct |
3 ms |
1364 KB |
Output is correct |
| 15 |
Correct |
2 ms |
1364 KB |
Output is correct |
| 16 |
Correct |
2 ms |
1364 KB |
Output is correct |
| 17 |
Correct |
3 ms |
1364 KB |
Output is correct |
| 18 |
Correct |
3 ms |
1364 KB |
Output is correct |
| 19 |
Correct |
3 ms |
1364 KB |
Output is correct |
| 20 |
Correct |
3 ms |
1364 KB |
Output is correct |
| 21 |
Correct |
4 ms |
1364 KB |
Output is correct |
| 22 |
Correct |
4 ms |
1364 KB |
Output is correct |
| 23 |
Correct |
3 ms |
1364 KB |
Output is correct |
| 24 |
Correct |
4 ms |
1372 KB |
Output is correct |
| 25 |
Correct |
4 ms |
1404 KB |
Output is correct |
| 26 |
Correct |
3 ms |
1444 KB |
Output is correct |
| 27 |
Correct |
5 ms |
1484 KB |
Output is correct |
| 28 |
Correct |
4 ms |
1524 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
1948 KB |
Output is correct |
| 2 |
Correct |
6 ms |
2084 KB |
Output is correct |
| 3 |
Correct |
23 ms |
4400 KB |
Output is correct |
| 4 |
Correct |
22 ms |
5432 KB |
Output is correct |
| 5 |
Correct |
13 ms |
5432 KB |
Output is correct |
| 6 |
Correct |
12 ms |
5456 KB |
Output is correct |
| 7 |
Correct |
19 ms |
6948 KB |
Output is correct |
| 8 |
Correct |
16 ms |
7720 KB |
Output is correct |
| 9 |
Correct |
13 ms |
7720 KB |
Output is correct |
| 10 |
Correct |
13 ms |
7720 KB |
Output is correct |
| 11 |
Correct |
23 ms |
9376 KB |
Output is correct |
| 12 |
Correct |
35 ms |
10416 KB |
Output is correct |
| 13 |
Correct |
14 ms |
10416 KB |
Output is correct |
| 14 |
Correct |
14 ms |
10464 KB |
Output is correct |
| 15 |
Correct |
18 ms |
11620 KB |
Output is correct |
| 16 |
Correct |
19 ms |
12408 KB |
Output is correct |
| 17 |
Correct |
21 ms |
13580 KB |
Output is correct |
| 18 |
Correct |
21 ms |
14524 KB |
Output is correct |
| 19 |
Correct |
26 ms |
15612 KB |
Output is correct |
| 20 |
Correct |
22 ms |
16616 KB |
Output is correct |
