#include<bits/stdc++.h>
#include "ricehub.h"
using namespace std;
using ll = long long;
ll Pre[100005];
ll Sum(ll l, ll r) {
if ( l == 0) return Pre[r];
return Pre[r] - Pre[l - 1];
}
int besthub(int R, int L, int X[], long long B) {
ll s;
int i, ans = 1, mn, l, r,lo, hi, mid;
for (i = 0; i < R; i ++) {
if ( i == 0) Pre[i] = X[i];
else Pre[i] = Pre[i - 1] + X[i];
}
for (int i = 1; i + 1 < R; i ++) {
lo = 0;
hi = R + 1;
while ( lo < hi ) {
mid = (lo +hi)/2;
l = i - mid;
r = i + mid;
if ( l < 0 || r >= R) {
hi =mid;
continue;
}
// cout << mid << " " <<l << " " << i << " " << i + 1 << " " << r<<" " <<Sum(i + 1, r) << " " << Sum(l, i) << endl;
if ( Sum(i + 1, r) - Sum(l, i - 1) <= B) lo = mid + 1;
else hi = mid;
}
mid = lo ;
// cout << mid << endl;
l = i - mid ;
r = i + mid;
s = Sum(i + 1, r - 1) - Sum(l + 1, i - 1) ;
// cout << l << " " << r <<" " << s << endl;
mn = INT_MAX;
if ( l >= 0) {
mn = min(mn, X[i] - X[l]);
}
if ( r < R) {
mn = min(mn, X[r] - X[i]);
}
if ( mn == INT_MAX) {
ans = max(ans, r - l - 1);
continue;
}
s = s + mn;
if (s <= B) {
ans = max(ans, r - l);
}
else ans = max(ans, r - l - 1);
}
return ans;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 3 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 4 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 5 |
Correct |
1 ms |
2396 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 2 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 3 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 4 |
Correct |
1 ms |
2404 KB |
Output is correct |
| 5 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 6 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 7 |
Correct |
1 ms |
2480 KB |
Output is correct |
| 8 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 9 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 10 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 11 |
Correct |
0 ms |
2392 KB |
Output is correct |
| 12 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 13 |
Correct |
1 ms |
2404 KB |
Output is correct |
| 14 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 15 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 16 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 17 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 18 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 19 |
Correct |
1 ms |
2488 KB |
Output is correct |
| 20 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 21 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 22 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 23 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 24 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 25 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 26 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 27 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 28 |
Correct |
1 ms |
2396 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 3 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 4 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 5 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 6 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 7 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 8 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 9 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 10 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 11 |
Correct |
1 ms |
2492 KB |
Output is correct |
| 12 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 13 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 14 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 15 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 16 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 17 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 18 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 19 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 20 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 21 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 22 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 23 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 24 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 25 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 26 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 27 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 28 |
Correct |
1 ms |
2532 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
2648 KB |
Output is correct |
| 2 |
Correct |
3 ms |
2652 KB |
Output is correct |
| 3 |
Correct |
14 ms |
2672 KB |
Output is correct |
| 4 |
Correct |
14 ms |
2648 KB |
Output is correct |
| 5 |
Correct |
6 ms |
2652 KB |
Output is correct |
| 6 |
Correct |
6 ms |
2672 KB |
Output is correct |
| 7 |
Correct |
13 ms |
2496 KB |
Output is correct |
| 8 |
Correct |
13 ms |
2648 KB |
Output is correct |
| 9 |
Correct |
5 ms |
2652 KB |
Output is correct |
| 10 |
Correct |
5 ms |
2652 KB |
Output is correct |
| 11 |
Correct |
14 ms |
2652 KB |
Output is correct |
| 12 |
Correct |
14 ms |
2652 KB |
Output is correct |
| 13 |
Correct |
9 ms |
2648 KB |
Output is correct |
| 14 |
Correct |
6 ms |
2648 KB |
Output is correct |
| 15 |
Correct |
11 ms |
2652 KB |
Output is correct |
| 16 |
Correct |
11 ms |
3276 KB |
Output is correct |
| 17 |
Correct |
13 ms |
3420 KB |
Output is correct |
| 18 |
Correct |
13 ms |
3420 KB |
Output is correct |
| 19 |
Correct |
14 ms |
3676 KB |
Output is correct |
| 20 |
Correct |
14 ms |
3532 KB |
Output is correct |
