# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1254072 | camil | Rice Hub (IOI11_ricehub) | C++20 | 0 ms | 0 KiB |
#pragma GCC optimize ("O3")
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
#define IOS ios::sync_with_stdio(false), cin.tie(0),cout.tie(0)
void solve() {
int n, L, k;
cin >> n >> L >> k;
int arr[n + 1];
for (int i = 1; i <= n; i++ ){
cin >> arr[i];
}
int l = 1;
int r = n;
int best = 1;
while(l <= r){
int m = (l + r) / 2;
int z = LLONG_MIN;
for (int i = 1; i <= n; i++ ){
int x = k;
int y = m;
int cnt = 1;
int a = i - 1, b = i + 1;
while (y--){
if(a >= 1 && a <= n && abs( arr[i] - arr[a] ) <= abs(arr[i] - arr[b]) && abs(arr[i] - arr[a] ) <= x ){
x -= abs(arr[i] - arr[a]);
a--;
cnt++;
}
else if(b >= 1 && b <= n && abs(arr[i] - arr[b] ) <= x ){
x -= abs(arr[i] - arr[b] );
b++;
cnt++;
}
}
z = max(z, cnt);
}
if(z >= m){
best = m;
l = m + 1;
}
else r = m - 1;
}
cout << best << endl;
}
signed main() {
IOS;
int t = 1;
//cin >> t;
while (t--) {
solve();
}
}