This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "ricehub.h"
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
int besthub(int n, int L, int X[], long long B) {
vector<ll> pref(n);
for (int i = 0; i < n; i++) {
pref[i] = (i > 0 ? pref[i - 1] : 0) + X[i];
}
auto sum = [&](int l, int r) -> ll {
if (l > r) return 0;
return pref[r] - (l > 0 ? pref[l - 1] : 0);
};
auto check = [&](int c) -> bool {
for (int lx = 0, rx = c - 1; rx < n; lx++, rx++) {
int mid = (lx + rx) >> 1;
ll need = 1ll * X[mid] * (mid - lx) - sum(lx, mid - 1);
need += sum(mid + 1, rx) - 1ll * X[mid] * (rx - mid);
if (need <= B) return true;
}
return false;
};
int lx = 1, rx = n, best = 0;
while (lx <= rx) {
int mid = (lx + rx) >> 1;
if (check(mid)) {
best = mid;
lx = mid + 1;
} else {
rx = mid - 1;
}
}
return best;
}
# | 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... |