#include <bits/stdc++.h> #include "ricehub.h" using namespace std; #define ll long long #define fi first #define se second #define pb push_back vector<ll> arr, pre, suf; int n; bool czy(int ile, ll b, int l) { for (int i = 1; i <= n; i++) { if (i - ile / 2 > 0 and i + (ile - 1) / 2 <= n) { ll kosztpr = pre[i + (ile-1)/2] - pre[i] - (ile-1)/2*arr[i]; ll kosztlw = suf[n - i + ile/2 + 1] - suf[n - i + 1] - ile/2*(l-arr[i]); if (kosztpr + kosztlw <= b) return 1; } } return 0; } int besthub(int r, int l, int x[], ll b) { n = r; int pocz = 0, kon = n, sr; pre.resize(n + 1); suf.resize(n + 1); arr.resize(n + 1); pre[0] = 0; suf[0] = 0; for (int i = 0; i < n; i++) arr[i + 1] = x[i]; for (int i = 1; i <= n; i++) { pre[i] = pre[i - 1] + arr[i]; suf[i] = suf[i - 1] + l - arr[n - i + 1]; } while (pocz < kon) { sr = (pocz + kon + 1) / 2; //cout << pocz << " " << kon << endl; if (czy(sr, b, l)) pocz = sr; else kon = sr - 1; } return pocz; } /*int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); ll r, l, b; cin >> r >> l; int x[r]; for (int i = 0; i < r; i++) { cin >> x[i]; } int q; cin >> q; while (q--) { cin >> b; cout << besthub(r, l, x, b) << endl; } }*/