solution

• $f(\vec{x}) = \mathrm{max}(\vec{x}) - \mathrm{min}(\vec{x})$とし、$B, C, D, E \in \mathbb{Z}$で$B \le C$とする。このとき$f(B, C, D, E) \le f(B - 1, C + 1, D, E)$である。

implementation

#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; (i) < int(n); ++ (i))
#define REP3(i, m, n) for (int i = (m); (i) < int(n); ++ (i))
#define ALL(x) begin(x), end(x)
using ll = long long;
using namespace std;
template <class T> inline void chmin(T & a, T const & b) { a = min(a, b); }

template <typename UnaryPredicate>
int64_t binsearch(int64_t l, int64_t r, UnaryPredicate p) {
assert (l <= r);
-- l;
while (r - l > 1) {
int64_t m = l + (r - l) / 2;  // to avoid overflow
(p(m) ? r : l) = m;
}
return r;
}

int main() {
// input
int n; cin >> n;
vector<ll> a(n);
REP (i, n) cin >> a[i];

// solve
vector<ll> acc(n + 1);
partial_sum(ALL(a), acc.begin() + 1);
REP (m, n + 1) {
int l0 = binsearch(0, m + 1, [&](int l) {
ll b = acc[l] - acc[0];
ll c = acc[m] - acc[l];
return b >= c;
});
int r0 = binsearch(m, n + 1, [&](int r) {
ll d = acc[r] - acc[m];
ll e = acc[n] - acc[r];
return d >= e;
});
REP3 (l, max(0, l0 - 3), min(m, l0 + 3) + 1) {
REP3 (r, max(m, r0 - 3), min(n, r0 + 3) + 1) {
ll b = acc[l] - acc[0];
ll c = acc[m] - acc[l];
ll d = acc[r] - acc[m];
ll e = acc[n] - acc[r];
array<ll, 4> bcde = {{ b, c, d, e }};