#include "ricehub.h"
#include <algorithm>
#define MAXN 100000
int cnt;
long long sum[MAXN + 1];
inline long long f(int p, int k, int n, int X[]) {
int rez = p;
for (int pas = 1 << 16; pas; pas >>= 1)
if (rez + pas <= n && X[rez + pas] <= X[p] + k)
rez += pas;
long long ans = sum[rez] - sum[p - 1] - 1LL * (rez - p + 1) * X[p];
cnt = rez - p + 1;
rez = p;
for (int pas = 1 << 16; pas; pas >>= 1)
if (rez - pas > 0 && X[rez - pas] >= X[p] - k)
rez -= pas;
cnt += p - rez;
ans += 1LL * (p - rez) * X[p] - (sum[p - 1] - sum[rez - 1]);
return ans;
}
inline int solve(int p, long long B, int n, int X[]) {
int rez = -1, cati = 0;
for (int pas = 1 << 29; pas; pas >>= 1)
if (f(p, rez + pas, n, X) <= B)
rez += pas, cati = cnt;
if (cati == n)
return cati;
return cati + (B - f(p, rez, n, X)) / (rez + 1);
}
int besthub(int R, int L, int X[], long long B) {
for (int i = R; i > 0; i--)
X[i] = X[i - 1];
for (int i = 1; i <= R; i++)
sum[i] = sum[i - 1] + X[i];
int ans = 0;
for (int i = 1; i <= R; i++)
ans = std::max(ans, solve(i, B, R, X));
return ans;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
384 KB |
Output is correct |
| 2 |
Correct |
2 ms |
256 KB |
Output is correct |
| 3 |
Correct |
2 ms |
384 KB |
Output is correct |
| 4 |
Correct |
2 ms |
384 KB |
Output is correct |
| 5 |
Correct |
2 ms |
384 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
256 KB |
Output is correct |
| 2 |
Correct |
2 ms |
384 KB |
Output is correct |
| 3 |
Correct |
2 ms |
256 KB |
Output is correct |
| 4 |
Correct |
2 ms |
384 KB |
Output is correct |
| 5 |
Correct |
2 ms |
256 KB |
Output is correct |
| 6 |
Correct |
2 ms |
384 KB |
Output is correct |
| 7 |
Correct |
2 ms |
384 KB |
Output is correct |
| 8 |
Correct |
2 ms |
384 KB |
Output is correct |
| 9 |
Correct |
3 ms |
384 KB |
Output is correct |
| 10 |
Correct |
2 ms |
256 KB |
Output is correct |
| 11 |
Correct |
2 ms |
256 KB |
Output is correct |
| 12 |
Correct |
1 ms |
384 KB |
Output is correct |
| 13 |
Correct |
2 ms |
384 KB |
Output is correct |
| 14 |
Correct |
3 ms |
384 KB |
Output is correct |
| 15 |
Correct |
2 ms |
384 KB |
Output is correct |
| 16 |
Correct |
3 ms |
384 KB |
Output is correct |
| 17 |
Correct |
2 ms |
384 KB |
Output is correct |
| 18 |
Correct |
2 ms |
384 KB |
Output is correct |
| 19 |
Correct |
3 ms |
256 KB |
Output is correct |
| 20 |
Correct |
2 ms |
256 KB |
Output is correct |
| 21 |
Correct |
3 ms |
256 KB |
Output is correct |
| 22 |
Correct |
3 ms |
256 KB |
Output is correct |
| 23 |
Correct |
4 ms |
256 KB |
Output is correct |
| 24 |
Correct |
3 ms |
256 KB |
Output is correct |
| 25 |
Correct |
3 ms |
256 KB |
Output is correct |
| 26 |
Correct |
3 ms |
256 KB |
Output is correct |
| 27 |
Correct |
3 ms |
256 KB |
Output is correct |
| 28 |
Correct |
3 ms |
384 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
3 ms |
256 KB |
Output is correct |
| 2 |
Correct |
3 ms |
384 KB |
Output is correct |
| 3 |
Correct |
3 ms |
384 KB |
Output is correct |
| 4 |
Correct |
4 ms |
384 KB |
Output is correct |
| 5 |
Correct |
2 ms |
256 KB |
Output is correct |
| 6 |
Correct |
4 ms |
384 KB |
Output is correct |
| 7 |
Correct |
5 ms |
384 KB |
Output is correct |
| 8 |
Correct |
4 ms |
384 KB |
Output is correct |
| 9 |
Correct |
4 ms |
384 KB |
Output is correct |
| 10 |
Correct |
3 ms |
384 KB |
Output is correct |
| 11 |
Correct |
3 ms |
384 KB |
Output is correct |
| 12 |
Correct |
3 ms |
256 KB |
Output is correct |
| 13 |
Correct |
4 ms |
256 KB |
Output is correct |
| 14 |
Correct |
3 ms |
384 KB |
Output is correct |
| 15 |
Correct |
3 ms |
256 KB |
Output is correct |
| 16 |
Correct |
2 ms |
256 KB |
Output is correct |
| 17 |
Correct |
4 ms |
384 KB |
Output is correct |
| 18 |
Correct |
4 ms |
256 KB |
Output is correct |
| 19 |
Correct |
4 ms |
384 KB |
Output is correct |
| 20 |
Correct |
4 ms |
384 KB |
Output is correct |
| 21 |
Correct |
12 ms |
504 KB |
Output is correct |
| 22 |
Correct |
10 ms |
384 KB |
Output is correct |
| 23 |
Correct |
11 ms |
368 KB |
Output is correct |
| 24 |
Correct |
11 ms |
384 KB |
Output is correct |
| 25 |
Correct |
10 ms |
384 KB |
Output is correct |
| 26 |
Correct |
12 ms |
384 KB |
Output is correct |
| 27 |
Correct |
16 ms |
384 KB |
Output is correct |
| 28 |
Correct |
13 ms |
384 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
52 ms |
760 KB |
Output is correct |
| 2 |
Correct |
51 ms |
700 KB |
Output is correct |
| 3 |
Correct |
207 ms |
2680 KB |
Output is correct |
| 4 |
Correct |
288 ms |
2652 KB |
Output is correct |
| 5 |
Correct |
135 ms |
1272 KB |
Output is correct |
| 6 |
Correct |
138 ms |
1280 KB |
Output is correct |
| 7 |
Correct |
178 ms |
2424 KB |
Output is correct |
| 8 |
Correct |
252 ms |
2280 KB |
Output is correct |
| 9 |
Correct |
171 ms |
1276 KB |
Output is correct |
| 10 |
Correct |
134 ms |
1272 KB |
Output is correct |
| 11 |
Correct |
224 ms |
2680 KB |
Output is correct |
| 12 |
Correct |
305 ms |
2560 KB |
Output is correct |
| 13 |
Correct |
161 ms |
1372 KB |
Output is correct |
| 14 |
Correct |
153 ms |
1316 KB |
Output is correct |
| 15 |
Correct |
160 ms |
2000 KB |
Output is correct |
| 16 |
Correct |
202 ms |
1996 KB |
Output is correct |
| 17 |
Correct |
172 ms |
2304 KB |
Output is correct |
| 18 |
Correct |
272 ms |
2368 KB |
Output is correct |
| 19 |
Correct |
198 ms |
2460 KB |
Output is correct |
| 20 |
Correct |
299 ms |
2560 KB |
Output is correct |
