#include "ricehub.h"
#include <iostream>
using namespace std;
#define ll long long
#define int ll
const int MAX = 1e5 + 7;
int n;
ll ar[MAX];
ll pfx[MAX];
ll budget;
int solve(int hub) //place a hub in ar[hub], calculate maximum amount of rice
{
int l1 = 1, r1 = hub;
while (l1 < r1)
{
int mid1 = (l1 + r1) / 2;
ll cost1 = (hub - mid1) * ar[hub] - (pfx[hub-1] - pfx[mid1 - 1]);
ll rt_cost = (pfx[n] - pfx[hub-1]) - (n - hub + 1) * ar[hub];
if (cost1 > budget) l1 = mid1 + 1;
else if (cost1 + rt_cost <= budget) r1 = mid1;
else
{
int l2 = hub, r2 = n;
while (l2 < r2)
{
int mid2 = (l2 + r2 + 1) / 2;
ll cost2 = (pfx[mid2] - pfx[hub-1]) - (mid2 - hub + 1) * ar[hub];
if (cost1 + cost2 <= budget) l2 = mid2;
else r2 = mid2 - 1;
}
if (ar[l2+1] - ar[hub] < ar[hub] - ar[mid1]) l1 = mid1 + 1;
else r1 = mid1;
}
}
ll cost1 = (hub - l1) * ar[hub] - (pfx[hub-1] - pfx[l1 - 1]);
int l2 = hub, r2 = n;
while (l2 < r2)
{
int mid2 = (l2 + r2 + 1) / 2;
ll cost2 = (pfx[mid2] - pfx[hub-1]) - (mid2 - hub + 1) * ar[hub];
if (cost1 + cost2 <= budget) l2 = mid2;
else r2 = mid2 - 1;
}
return l2 - l1 + 1;
}
int32_t besthub(int32_t R, int32_t L, int32_t X[], long long B)
{
n = R;
budget = B;
for (int i = 1; i <= R; ++i)
{
ar[i] = X[i-1];
pfx[i] = pfx[i-1] + X[i-1];
}
int res = 0;
for (int i = 1; i <= R; ++i)
{
//cerr << i << ": " << solve(i) << '\n';
res = max(res, solve(i));
}
return res;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
364 KB |
Output is correct |
| 3 |
Correct |
1 ms |
364 KB |
Output is correct |
| 4 |
Correct |
1 ms |
364 KB |
Output is correct |
| 5 |
Correct |
1 ms |
364 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
364 KB |
Output is correct |
| 3 |
Correct |
1 ms |
364 KB |
Output is correct |
| 4 |
Correct |
1 ms |
364 KB |
Output is correct |
| 5 |
Correct |
1 ms |
364 KB |
Output is correct |
| 6 |
Correct |
2 ms |
364 KB |
Output is correct |
| 7 |
Correct |
1 ms |
364 KB |
Output is correct |
| 8 |
Correct |
1 ms |
364 KB |
Output is correct |
| 9 |
Correct |
1 ms |
364 KB |
Output is correct |
| 10 |
Correct |
1 ms |
364 KB |
Output is correct |
| 11 |
Correct |
1 ms |
364 KB |
Output is correct |
| 12 |
Correct |
1 ms |
364 KB |
Output is correct |
| 13 |
Correct |
1 ms |
364 KB |
Output is correct |
| 14 |
Correct |
1 ms |
364 KB |
Output is correct |
| 15 |
Correct |
1 ms |
364 KB |
Output is correct |
| 16 |
Correct |
1 ms |
364 KB |
Output is correct |
| 17 |
Correct |
2 ms |
364 KB |
Output is correct |
| 18 |
Correct |
1 ms |
364 KB |
Output is correct |
| 19 |
Correct |
1 ms |
364 KB |
Output is correct |
| 20 |
Correct |
1 ms |
364 KB |
Output is correct |
| 21 |
Correct |
1 ms |
364 KB |
Output is correct |
| 22 |
Correct |
1 ms |
364 KB |
Output is correct |
| 23 |
Correct |
1 ms |
364 KB |
Output is correct |
| 24 |
Correct |
1 ms |
364 KB |
Output is correct |
| 25 |
Correct |
1 ms |
364 KB |
Output is correct |
| 26 |
Correct |
1 ms |
364 KB |
Output is correct |
| 27 |
Correct |
1 ms |
364 KB |
Output is correct |
| 28 |
Correct |
2 ms |
364 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
364 KB |
Output is correct |
| 3 |
Correct |
1 ms |
364 KB |
Output is correct |
| 4 |
Correct |
2 ms |
364 KB |
Output is correct |
| 5 |
Correct |
1 ms |
364 KB |
Output is correct |
| 6 |
Correct |
2 ms |
364 KB |
Output is correct |
| 7 |
Correct |
2 ms |
364 KB |
Output is correct |
| 8 |
Correct |
2 ms |
364 KB |
Output is correct |
| 9 |
Correct |
1 ms |
364 KB |
Output is correct |
| 10 |
Correct |
1 ms |
364 KB |
Output is correct |
| 11 |
Correct |
1 ms |
364 KB |
Output is correct |
| 12 |
Correct |
1 ms |
364 KB |
Output is correct |
| 13 |
Correct |
1 ms |
364 KB |
Output is correct |
| 14 |
Correct |
2 ms |
364 KB |
Output is correct |
| 15 |
Correct |
1 ms |
364 KB |
Output is correct |
| 16 |
Correct |
1 ms |
364 KB |
Output is correct |
| 17 |
Correct |
2 ms |
364 KB |
Output is correct |
| 18 |
Correct |
2 ms |
364 KB |
Output is correct |
| 19 |
Correct |
1 ms |
364 KB |
Output is correct |
| 20 |
Correct |
2 ms |
364 KB |
Output is correct |
| 21 |
Correct |
4 ms |
640 KB |
Output is correct |
| 22 |
Correct |
4 ms |
492 KB |
Output is correct |
| 23 |
Correct |
2 ms |
492 KB |
Output is correct |
| 24 |
Correct |
4 ms |
512 KB |
Output is correct |
| 25 |
Correct |
3 ms |
492 KB |
Output is correct |
| 26 |
Correct |
4 ms |
492 KB |
Output is correct |
| 27 |
Correct |
5 ms |
492 KB |
Output is correct |
| 28 |
Correct |
5 ms |
492 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
10 ms |
876 KB |
Output is correct |
| 2 |
Correct |
12 ms |
876 KB |
Output is correct |
| 3 |
Correct |
26 ms |
3308 KB |
Output is correct |
| 4 |
Correct |
98 ms |
3308 KB |
Output is correct |
| 5 |
Correct |
25 ms |
1644 KB |
Output is correct |
| 6 |
Correct |
29 ms |
1772 KB |
Output is correct |
| 7 |
Correct |
24 ms |
3052 KB |
Output is correct |
| 8 |
Correct |
84 ms |
3052 KB |
Output is correct |
| 9 |
Correct |
54 ms |
1644 KB |
Output is correct |
| 10 |
Correct |
54 ms |
1644 KB |
Output is correct |
| 11 |
Correct |
24 ms |
3308 KB |
Output is correct |
| 12 |
Correct |
95 ms |
3308 KB |
Output is correct |
| 13 |
Correct |
35 ms |
1644 KB |
Output is correct |
| 14 |
Correct |
34 ms |
1644 KB |
Output is correct |
| 15 |
Correct |
19 ms |
2540 KB |
Output is correct |
| 16 |
Correct |
69 ms |
2540 KB |
Output is correct |
| 17 |
Correct |
23 ms |
3052 KB |
Output is correct |
| 18 |
Correct |
83 ms |
3052 KB |
Output is correct |
| 19 |
Correct |
24 ms |
3208 KB |
Output is correct |
| 20 |
Correct |
97 ms |
3308 KB |
Output is correct |
