# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1241864 | mrivera11 | Message (IOI24_message) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int r;
ll l, b;
vector<ll> x, pr;
bool cn(int k) {
for (int i = 0; i + k <= r; ++i) {
int j = i + k - 1;
int m = (i + j) / 2;
ll L = x[m] * (m - i) - (pr[m - 1] - (i > 0 ? pr[i - 1] : 0));
ll R = (pr[j] - pr[m]) - x[m] * (j - m);
if (L + R <= b) return true;
}
return false;
}
int bh(int r_, int l_, vector<int>& x_, ll b_) {
r = r_; l = l_; b = b_;
x = vector<ll>(x_.begin(), x_.end());
pr.resize(r);
pr[0] = x[0];
for (int i = 1; i < r; ++i) pr[i] = pr[i - 1] + x[i];
int lo = 1, hi = r, ans = 1;
while (lo <= hi) {
int k = (lo + hi) / 2;
if (cn(k)) ans = k, lo = k + 1;
else hi = k - 1;
}
return ans;
}
int main() {
int r = 5; ll l = 20, b = 6;
vector<int> x = {1, 2, 10, 12, 14};
cout << bh(r, l, x, b) << endl;
}