#include <bits/stdc++.h>
using namespace std;
#include "ricehub.h"
#define int long long
int prefix[100003], suffix[100003];
int r, l, pos[100003];
int b;
int costLeft(int x, int g, int d) {
int dst = x - pos[d];
dst *= (d - g + 1LL);
dst += suffix[g] - suffix[d+1] - (l - pos[d]) * (d - g + 1LL);
return dst;
}
int costRight(int x, int g, int d) {
int dst = pos[g] - x;
dst *= (d - g + 1LL);
dst += prefix[d] - prefix[g-1] - pos[g] * (d - g + 1LL);
return dst;
}
int cost(int g, int d) {
int x = pos[(g + d) / 2];
return costLeft(x, g, (g+d)/2) + costRight(x, (g+d)/2+1, d);
}
bool ok(int g, int d) {
return cost(g, d) <= b;
}
int32_t besthub(int32_t R, int32_t L, int32_t *X, long long B) {
for(int i = 1; i <= R; i++) pos[i] = X[i-1];
r = R, l = L, b = B;
prefix[0] = suffix[R+1] = 0;
for(int i = 1; i <= R; i++)
prefix[i] = prefix[i-1] + pos[i];
for(int i = R; i >= 1; i--)
suffix[i] = suffix[i+1] + l - pos[i];
int ans = 1;
int j = -1;
for(int i = 1; i <= R; i++) {
if(j < i) {
j = i;
}
ans = max(ans, j-i+1);
while(j+1 <= R and ok(i, j+1)) {
ans = max(ans, (j+1-i+1));
j++;
}
}
return ans;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
248 KB |
Output is correct |
| 2 |
Correct |
2 ms |
356 KB |
Output is correct |
| 3 |
Correct |
3 ms |
560 KB |
Output is correct |
| 4 |
Correct |
1 ms |
560 KB |
Output is correct |
| 5 |
Correct |
2 ms |
560 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
3 ms |
560 KB |
Output is correct |
| 2 |
Correct |
2 ms |
560 KB |
Output is correct |
| 3 |
Correct |
2 ms |
620 KB |
Output is correct |
| 4 |
Correct |
2 ms |
620 KB |
Output is correct |
| 5 |
Correct |
2 ms |
620 KB |
Output is correct |
| 6 |
Correct |
3 ms |
620 KB |
Output is correct |
| 7 |
Correct |
2 ms |
736 KB |
Output is correct |
| 8 |
Correct |
3 ms |
736 KB |
Output is correct |
| 9 |
Correct |
3 ms |
736 KB |
Output is correct |
| 10 |
Correct |
2 ms |
736 KB |
Output is correct |
| 11 |
Correct |
3 ms |
744 KB |
Output is correct |
| 12 |
Correct |
4 ms |
764 KB |
Output is correct |
| 13 |
Correct |
2 ms |
816 KB |
Output is correct |
| 14 |
Correct |
3 ms |
816 KB |
Output is correct |
| 15 |
Correct |
2 ms |
816 KB |
Output is correct |
| 16 |
Correct |
2 ms |
816 KB |
Output is correct |
| 17 |
Correct |
2 ms |
816 KB |
Output is correct |
| 18 |
Correct |
2 ms |
840 KB |
Output is correct |
| 19 |
Correct |
2 ms |
840 KB |
Output is correct |
| 20 |
Correct |
2 ms |
840 KB |
Output is correct |
| 21 |
Correct |
2 ms |
840 KB |
Output is correct |
| 22 |
Correct |
2 ms |
840 KB |
Output is correct |
| 23 |
Correct |
2 ms |
840 KB |
Output is correct |
| 24 |
Correct |
2 ms |
840 KB |
Output is correct |
| 25 |
Correct |
2 ms |
840 KB |
Output is correct |
| 26 |
Correct |
3 ms |
840 KB |
Output is correct |
| 27 |
Correct |
2 ms |
840 KB |
Output is correct |
| 28 |
Correct |
2 ms |
840 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
840 KB |
Output is correct |
| 2 |
Correct |
3 ms |
840 KB |
Output is correct |
| 3 |
Correct |
2 ms |
840 KB |
Output is correct |
| 4 |
Correct |
2 ms |
840 KB |
Output is correct |
| 5 |
Correct |
2 ms |
840 KB |
Output is correct |
| 6 |
Correct |
2 ms |
840 KB |
Output is correct |
| 7 |
Correct |
2 ms |
840 KB |
Output is correct |
| 8 |
Correct |
2 ms |
840 KB |
Output is correct |
| 9 |
Correct |
2 ms |
848 KB |
Output is correct |
| 10 |
Correct |
2 ms |
848 KB |
Output is correct |
| 11 |
Correct |
3 ms |
856 KB |
Output is correct |
| 12 |
Correct |
4 ms |
876 KB |
Output is correct |
| 13 |
Correct |
2 ms |
912 KB |
Output is correct |
| 14 |
Correct |
2 ms |
924 KB |
Output is correct |
| 15 |
Correct |
2 ms |
932 KB |
Output is correct |
| 16 |
Correct |
2 ms |
936 KB |
Output is correct |
| 17 |
Correct |
2 ms |
940 KB |
Output is correct |
| 18 |
Correct |
2 ms |
952 KB |
Output is correct |
| 19 |
Correct |
3 ms |
956 KB |
Output is correct |
| 20 |
Correct |
2 ms |
964 KB |
Output is correct |
| 21 |
Correct |
3 ms |
1100 KB |
Output is correct |
| 22 |
Correct |
4 ms |
1124 KB |
Output is correct |
| 23 |
Correct |
3 ms |
1148 KB |
Output is correct |
| 24 |
Correct |
3 ms |
1180 KB |
Output is correct |
| 25 |
Correct |
4 ms |
1212 KB |
Output is correct |
| 26 |
Correct |
3 ms |
1252 KB |
Output is correct |
| 27 |
Correct |
2 ms |
1332 KB |
Output is correct |
| 28 |
Correct |
4 ms |
1460 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
5 ms |
1756 KB |
Output is correct |
| 2 |
Correct |
9 ms |
1760 KB |
Output is correct |
| 3 |
Correct |
19 ms |
3932 KB |
Output is correct |
| 4 |
Correct |
21 ms |
3932 KB |
Output is correct |
| 5 |
Correct |
9 ms |
3932 KB |
Output is correct |
| 6 |
Correct |
16 ms |
3932 KB |
Output is correct |
| 7 |
Correct |
21 ms |
3956 KB |
Output is correct |
| 8 |
Correct |
37 ms |
4016 KB |
Output is correct |
| 9 |
Correct |
14 ms |
4016 KB |
Output is correct |
| 10 |
Correct |
9 ms |
4016 KB |
Output is correct |
| 11 |
Correct |
21 ms |
4016 KB |
Output is correct |
| 12 |
Correct |
21 ms |
4016 KB |
Output is correct |
| 13 |
Correct |
11 ms |
4016 KB |
Output is correct |
| 14 |
Correct |
10 ms |
4016 KB |
Output is correct |
| 15 |
Correct |
21 ms |
4016 KB |
Output is correct |
| 16 |
Correct |
23 ms |
4016 KB |
Output is correct |
| 17 |
Correct |
20 ms |
4016 KB |
Output is correct |
| 18 |
Correct |
27 ms |
4016 KB |
Output is correct |
| 19 |
Correct |
20 ms |
4016 KB |
Output is correct |
| 20 |
Correct |
21 ms |
4016 KB |
Output is correct |
