先考虑贪心，令 \(f(x, k)\) 为满足 \(\sum\limits_{i = 1}^k s_i = x, s_i\in \mathbb{N}_+\) 的 \(s\) 的 \(\sum\limits_{i = 1}^k s_i^2\) 的最小值。
也就是题目中在两个固定的点中放 \(k - 1\) 个点这两个点中的最小贡献。
平均分肯定是最优的，可以通过 \(x\bmod k\) 的值 \(O(1)\) 算出 \(f(x, k)\)。
那么就可以考虑令当前两个点中的一段已经分了 \(k\) 段了（初始就是分了 \(1\) 段），贡献为 \(f(x, k)\)。
如果花费 \(1\) 的代价，会分成 \(k + 1\) 段，贡献为 \(f(x, k + 1)\)。
显然会去选择 \(f(x, k) - f(x, k + 1)\) 最大的一个，因为代价相同，贡献肯定越少越好，且能发现 \(f(x, k) - f(x, k + 1)\) 随着 \(k\) 的增长而减少，选这个肯定不会比还没有选到的操作劣。
直接贪心可能会因为极小的 \(m\) 导致贪心次数过多而 \(\text{T}\) 掉。
考虑到令 \(g(i)\) 为代价为 \(i\) 时最小的贡献。
根据上面的贪心，能知道每次选的肯定都是没选的之中最优的，也就是贡献减少的最多的。
于是可以得到 \(g(i - 1) - g(i)\le g(i - 2) - g(i - 1)\)，即第 \(i\) 次花费 \(1\) 代价减少的贡献肯定不会超过第 \(i - 1\) 次减少的贡献。
于是就可以考虑通过二分 \(g(i - 1) - g(i)\) 的值 \(x\)，并只操作减少的贡献 \(\ge x\) 的操作。
可以根据最后的结果 \(sum\) 和选出的个数 \(cnt\) 判断 \(sum\) 与 \(m\) 的大小关系根据 \(cnt\) 得到答案。
注意可能有多个减少的贡献 \(= x\) 的操作，在最后得到的 \(sum\) 是这些操作都用了的值，但如果能少用几个操作使得 \(sum\) 依然 \(\le m\) 那就可以撤销这几次操作。
这种方法的另一种解释就是考虑考虑 \((i, g(i))\) 组成了一个下凸壳，二分斜率看切点 \(u\) 的 \(g(u)\) 是否 \(\le m\)。
对于找到减少贡献 \(\ge x\) 的操作，可以通过二分得到。
注意特判不进行操作就已经满足条件的情况。
时间复杂度 \(O(n\log n\log V^2)\)，\(V\) 是 \(a_i\) 的值域。
#include<bits/stdc++.h>
using i64 = long long;
inline i64 f(i64 x, i64 k) {
if (x % k == 0) return x / k * x;
i64 c1 = x % k, c2 = k - c1;
return (x / k) * (x / k) * c2 + (x / k + 1) * (x / k + 1) * c1;
}
const int maxn = 2e5 + 10;
int n; i64 m;
i64 a[maxn];
i64 sum, cnt;
void solve(i64 w) {
sum = cnt = 0;
for (int i = 1; i <= n; i++) {
i64 l = 2, r = a[i], t = 1;
while (l <= r) {
i64 mid = (l + r) >> 1;
f(a[i], mid) - f(a[i], mid - 1) - w <= 0 ? (t = mid, l = mid + 1) : (r = mid - 1);
}
sum += f(a[i], t), cnt += t - 1;
}
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%lld", &a[i]);
for (int i = n; i; i--) a[i] -= a[i - 1];
i64 l = 0;
for (int i = 1; i <= n; i++) l = std::max(l, a[i]);
l *= l, l *= -1;
scanf("%lld", &m);
solve(l);
if (sum <= m) return puts("0"), 0;
i64 r = -1, ans = m;
while (l <= r) {
i64 mid = (l + r) >> 1;
solve(mid);
sum <= m ? (ans = cnt - (sum - m) / mid, r = mid - 1) : (l = mid + 1);
}
printf("%lld\n", ans);
return 0;
}