#include <bits/stdc++.h>
using namespace std;
int besthub(int n, int m, int a[], long long b) {
vector<long long> prfx(n);
prfx[0] = a[0];
for (long long i = 1; i < n; ++i) {
prfx[i] = prfx[i - 1] + a[i];
}
auto getPrfx = [&](long long l, long long r) -> long long {
if (l > r) return 0;
long long left = (l == 0) ? 0 : prfx[l - 1];
long long right = prfx[r];
return right - left;
};
long long res = 1;
long long l = 0, r = 0;
while (r < n) {
long long mid = (l + r) / 2;
long long s = getPrfx(l, r) - a[mid];
long long s1 = getPrfx(l, mid - 1);
long long s2 = getPrfx(mid + 1, r);
long long d1 = mid - l;
long long d2 = r - mid;
long long score = s2 - 1LL * d2 * a[mid] + (1LL * d1 * a[mid] - s1);
if (score <= b) {
res = max(res, r - l + 1);
++r;
} else {
++l;
}
}
return (int)res;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |