// #include "ricehub.h"
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e5 + 2;
/// You can declare global variables here if necessary.
/// But you are NOT allowed to write main function.
vector<int> a;
ll dis[N];
int r, l;
ll money;
bool check(int num)
{
for (int i = 1; i <= (r - num + 1); i++)
{
int j = i + num - 1;
int mid = (j + i) / 2;
ll ans = (dis[j] - dis[mid] - 1ll * a[mid] * (j - mid)) + (1ll * a[mid] * (mid - i + 1) - (dis[mid] - dis[i - 1]));
// cout << i << " " << j << " " << mid << " " << ans << '\n';
if (ans <= money)
return true;
}
return false;
}
/// You have to implement the below functions:
int besthub(int g, int h, int x[], ll b)
{
r = g;
a.push_back(0);
for (int i = 0; i < r; i++)
a.push_back(x[i]);
for (int i = 1; i <= r; i++)
dis[i] = dis[i - 1] + a[i];
money = b;
int low = 1, high = r, mid, ans = -1;
while (low <= high)
{
mid = (low + high) / 2;
if (check(mid))
{
ans = mid;
low = mid + 1;
}
else
high = mid - 1;
}
return ans;
}
/*
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> r >> l;
vector<int> tmp;
for (int i = 1; i <= r; i++)
{
int x;
cin >> x;
tmp.push_back(x);
}
cin >> money;
cout << besthub(r, l, tmp, money);
return 0;
}
*/
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2648 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 |
2496 KB |
Output is correct |
5 |
Correct |
1 ms |
2648 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
2396 KB |
Output is correct |
2 |
Correct |
1 ms |
2396 KB |
Output is correct |
3 |
Correct |
0 ms |
2396 KB |
Output is correct |
4 |
Correct |
0 ms |
2396 KB |
Output is correct |
5 |
Correct |
1 ms |
2396 KB |
Output is correct |
6 |
Correct |
1 ms |
2396 KB |
Output is correct |
7 |
Correct |
0 ms |
2396 KB |
Output is correct |
8 |
Correct |
0 ms |
2396 KB |
Output is correct |
9 |
Correct |
1 ms |
2648 KB |
Output is correct |
10 |
Correct |
0 ms |
2396 KB |
Output is correct |
11 |
Correct |
1 ms |
2396 KB |
Output is correct |
12 |
Correct |
0 ms |
2396 KB |
Output is correct |
13 |
Correct |
1 ms |
2396 KB |
Output is correct |
14 |
Correct |
0 ms |
2496 KB |
Output is correct |
15 |
Correct |
0 ms |
2648 KB |
Output is correct |
16 |
Correct |
0 ms |
2396 KB |
Output is correct |
17 |
Correct |
0 ms |
2396 KB |
Output is correct |
18 |
Correct |
0 ms |
2396 KB |
Output is correct |
19 |
Correct |
0 ms |
2392 KB |
Output is correct |
20 |
Correct |
0 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 |
2492 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2396 KB |
Output is correct |
2 |
Correct |
1 ms |
2496 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 |
2396 KB |
Output is correct |
7 |
Correct |
1 ms |
2392 KB |
Output is correct |
8 |
Correct |
1 ms |
2396 KB |
Output is correct |
9 |
Correct |
0 ms |
2396 KB |
Output is correct |
10 |
Correct |
1 ms |
2396 KB |
Output is correct |
11 |
Correct |
1 ms |
2396 KB |
Output is correct |
12 |
Correct |
1 ms |
2504 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 |
2396 KB |
Output is correct |
21 |
Correct |
1 ms |
2508 KB |
Output is correct |
22 |
Correct |
1 ms |
2396 KB |
Output is correct |
23 |
Correct |
1 ms |
2520 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 |
2392 KB |
Output is correct |
28 |
Correct |
1 ms |
2396 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
2908 KB |
Output is correct |
2 |
Correct |
3 ms |
2908 KB |
Output is correct |
3 |
Correct |
10 ms |
4056 KB |
Output is correct |
4 |
Correct |
12 ms |
4056 KB |
Output is correct |
5 |
Correct |
6 ms |
3148 KB |
Output is correct |
6 |
Correct |
5 ms |
3540 KB |
Output is correct |
7 |
Correct |
8 ms |
3800 KB |
Output is correct |
8 |
Correct |
8 ms |
3752 KB |
Output is correct |
9 |
Correct |
5 ms |
3288 KB |
Output is correct |
10 |
Correct |
5 ms |
3236 KB |
Output is correct |
11 |
Correct |
10 ms |
4056 KB |
Output is correct |
12 |
Correct |
10 ms |
4056 KB |
Output is correct |
13 |
Correct |
6 ms |
3236 KB |
Output is correct |
14 |
Correct |
6 ms |
3288 KB |
Output is correct |
15 |
Correct |
11 ms |
4012 KB |
Output is correct |
16 |
Correct |
7 ms |
3800 KB |
Output is correct |
17 |
Correct |
9 ms |
4008 KB |
Output is correct |
18 |
Correct |
9 ms |
4056 KB |
Output is correct |
19 |
Correct |
9 ms |
4056 KB |
Output is correct |
20 |
Correct |
9 ms |
4132 KB |
Output is correct |