#include <bits/stdc++.h>
typedef long long ll;
const int N = 3e3 + 5;

int n, m, que[N], l, r;
ll a[N], f[N], g[N];
ll X(int i) { return a[i]; }
ll Y(int i) { return f[i] + a[i] * a[i]; }
double K(int i, int j) { return double(Y(i) - Y(j)) / (X(i) - X(j)); }

int check(ll mid) {
    l = r = 0;
    for (int i = 1; i <= n; ++i) {
        while (l < r && K(que[l], que[l + 1]) < a[i] * 2.0) ++l;
        f[i] = f[que[l]] + (a[i] - a[que[l]]) * (a[i] - a[que[l]]) + mid;
        g[i] = g[que[l]] + 1;
        while (l < r && K(que[r - 1], que[r]) >= K(que[r - 1], i)) --r;
        que[++r] = i; 
    } return g[n];
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i)
        scanf("%lld", a + i), a[i] += a[i - 1];
    ll l = 0, r = a[n] * a[n], mid;
    while (l < r)
        if (check(mid = l + r >> 1) <= m) r = mid;
        else l = mid + 1;
    check(r); printf("%lld", (f[n] - r * m) * m - a[n] * a[n]);
    return 0;
}

为什么我将第 15 行的

while (l < r && K(que[l], que[l + 1]) < a[i] * 2.0) ++l;

改成

while (l < r && K(que[l], que[l + 1]) <= a[i] * 2.0) ++l;

（把 $<$ 改成了 $\le$）就 90 pts 了？