#include <bits/stdc++.h>
#include "ricehub.h"
using namespace std;
long long pos[100100], qs[100100];
long long cost_r(int i, int j)
{
if(i > j) return 0;
return qs[j] - qs[i] - pos[i]*(j-i);
}
long long cost_l(int i, int j)
{
return pos[j]*(j-i) - qs[j-1] + qs[i-1];
}
int solve_l(int i, long long bl)
{
int l = 1, r = i;
while(l != r)
{
int mid = (l+r)>>1;
if(cost_l(mid, i) <= bl) r = mid;
else l = mid+1;
}
return i-l;
}
int besthub(int R, int L, int X[], long long B)
{
int ans = 1;
for(int i=0 ; i<R ; i++)
{
pos[i+1] = X[i];
qs[i+1] = qs[i] + X[i];
}
for(int i=1 ; i<=R ; i++)
{
int l=i, r = R;
while(l != r)
{
int mid = (l+r+1)>>1;
long long br = cost_r(i, mid);
if(br > B)
{
r = mid-1;
continue ;
}
long long bl = B - br;
int hl = solve_l(i, bl);
if(mid - i + hl >= mid - 1 - i + solve_l(i, B - cost_r(i, mid-1))) l = mid;
else r = mid-1;
}
ans = max(ans, 1+l-i + solve_l(i, B - cost_r(i, l)));
}
return ans;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| 2 |
Correct |
4 ms |
384 KB |
Output is correct |
| 3 |
Correct |
5 ms |
384 KB |
Output is correct |
| 4 |
Correct |
5 ms |
384 KB |
Output is correct |
| 5 |
Correct |
5 ms |
384 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
4 ms |
384 KB |
Output is correct |
| 2 |
Correct |
5 ms |
384 KB |
Output is correct |
| 3 |
Correct |
4 ms |
384 KB |
Output is correct |
| 4 |
Correct |
5 ms |
384 KB |
Output is correct |
| 5 |
Correct |
5 ms |
384 KB |
Output is correct |
| 6 |
Correct |
4 ms |
384 KB |
Output is correct |
| 7 |
Correct |
5 ms |
384 KB |
Output is correct |
| 8 |
Correct |
5 ms |
384 KB |
Output is correct |
| 9 |
Correct |
4 ms |
384 KB |
Output is correct |
| 10 |
Correct |
5 ms |
384 KB |
Output is correct |
| 11 |
Correct |
5 ms |
384 KB |
Output is correct |
| 12 |
Correct |
4 ms |
384 KB |
Output is correct |
| 13 |
Correct |
5 ms |
384 KB |
Output is correct |
| 14 |
Correct |
4 ms |
384 KB |
Output is correct |
| 15 |
Correct |
5 ms |
384 KB |
Output is correct |
| 16 |
Correct |
5 ms |
384 KB |
Output is correct |
| 17 |
Correct |
5 ms |
384 KB |
Output is correct |
| 18 |
Correct |
4 ms |
384 KB |
Output is correct |
| 19 |
Correct |
4 ms |
384 KB |
Output is correct |
| 20 |
Correct |
4 ms |
384 KB |
Output is correct |
| 21 |
Correct |
5 ms |
384 KB |
Output is correct |
| 22 |
Correct |
5 ms |
384 KB |
Output is correct |
| 23 |
Correct |
5 ms |
384 KB |
Output is correct |
| 24 |
Correct |
5 ms |
360 KB |
Output is correct |
| 25 |
Correct |
5 ms |
384 KB |
Output is correct |
| 26 |
Correct |
5 ms |
384 KB |
Output is correct |
| 27 |
Correct |
5 ms |
384 KB |
Output is correct |
| 28 |
Correct |
5 ms |
384 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| 2 |
Correct |
5 ms |
384 KB |
Output is correct |
| 3 |
Correct |
5 ms |
384 KB |
Output is correct |
| 4 |
Correct |
5 ms |
384 KB |
Output is correct |
| 5 |
Correct |
5 ms |
384 KB |
Output is correct |
| 6 |
Correct |
5 ms |
384 KB |
Output is correct |
| 7 |
Correct |
5 ms |
384 KB |
Output is correct |
| 8 |
Correct |
5 ms |
384 KB |
Output is correct |
| 9 |
Correct |
5 ms |
384 KB |
Output is correct |
| 10 |
Correct |
5 ms |
384 KB |
Output is correct |
| 11 |
Correct |
5 ms |
384 KB |
Output is correct |
| 12 |
Correct |
6 ms |
384 KB |
Output is correct |
| 13 |
Correct |
5 ms |
384 KB |
Output is correct |
| 14 |
Correct |
5 ms |
384 KB |
Output is correct |
| 15 |
Correct |
5 ms |
384 KB |
Output is correct |
| 16 |
Correct |
5 ms |
384 KB |
Output is correct |
| 17 |
Correct |
5 ms |
384 KB |
Output is correct |
| 18 |
Correct |
5 ms |
384 KB |
Output is correct |
| 19 |
Correct |
5 ms |
384 KB |
Output is correct |
| 20 |
Correct |
5 ms |
384 KB |
Output is correct |
| 21 |
Correct |
9 ms |
512 KB |
Output is correct |
| 22 |
Correct |
9 ms |
512 KB |
Output is correct |
| 23 |
Correct |
8 ms |
512 KB |
Output is correct |
| 24 |
Correct |
9 ms |
512 KB |
Output is correct |
| 25 |
Correct |
9 ms |
512 KB |
Output is correct |
| 26 |
Correct |
9 ms |
512 KB |
Output is correct |
| 27 |
Correct |
11 ms |
512 KB |
Output is correct |
| 28 |
Correct |
11 ms |
512 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
16 ms |
896 KB |
Output is correct |
| 2 |
Correct |
16 ms |
896 KB |
Output is correct |
| 3 |
Correct |
115 ms |
3328 KB |
Output is correct |
| 4 |
Correct |
179 ms |
3328 KB |
Output is correct |
| 5 |
Correct |
32 ms |
1664 KB |
Output is correct |
| 6 |
Correct |
33 ms |
1664 KB |
Output is correct |
| 7 |
Correct |
111 ms |
3148 KB |
Output is correct |
| 8 |
Correct |
149 ms |
3072 KB |
Output is correct |
| 9 |
Correct |
96 ms |
1656 KB |
Output is correct |
| 10 |
Correct |
97 ms |
1652 KB |
Output is correct |
| 11 |
Correct |
116 ms |
3320 KB |
Output is correct |
| 12 |
Correct |
176 ms |
3320 KB |
Output is correct |
| 13 |
Correct |
47 ms |
1664 KB |
Output is correct |
| 14 |
Correct |
47 ms |
1664 KB |
Output is correct |
| 15 |
Correct |
81 ms |
2560 KB |
Output is correct |
| 16 |
Correct |
127 ms |
2560 KB |
Output is correct |
| 17 |
Correct |
101 ms |
3064 KB |
Output is correct |
| 18 |
Correct |
150 ms |
3072 KB |
Output is correct |
| 19 |
Correct |
107 ms |
3200 KB |
Output is correct |
| 20 |
Correct |
166 ms |
3276 KB |
Output is correct |
