根据题意可以得到以下的方程。
\(f_{i, j}\) 表示前 \(j\) 个分成 \(i\) 段的答案。
\[f_{i, j} = \max \{f_{i-1, k} + (sum_j - sum_k) \times sum_k\}
\]
看到这个典型的 2D/1D, 肯定有很多人要开始大力斜率优化了。
但是这里斜率优化又要推一堆式子，又要担心浮点数误差啥的，式子复杂了万一推错了或者敲错了怎么办？这里介绍以前从未见过的科技，决策单调性分治！
因为决策是单调的，那么我们每次的决策区间就能定下来，把它塞进分治的模板里就好了。
模板大概长这样：
\[\boxed{
\begin{aligned}
& \text{solve}(l,r,L,R) :\& \kern{2em}\text{if}(l>r) \ \text{exit} \& \kern{2em}mid \leftarrow (l+r) / 2 \& \kern{2em}pos \leftarrow \text{query}[L,R,mid] \& \kern{2em}f[mid] \leftarrow g(pos) \& \kern{2em} \text{solve}(l,mid-1,L,pos), \text{solve}(mid+1,r,pos,R)
\end{aligned}
}
\]
对于这道题，还要加上一维，这一维直接枚举就可以了，因为一定是上一层转移过来的，如果同一层也能转移，那恐怕还得套一层 cdq。
第一次写这种题，居然一遍过，代码留念。
#include <cstdio>
#include <algorithm>
#define int long long
const int N = 100005;
int n, m, sum[N], f[205][N], ans[N], pre[205][N];
void solve(int l, int r, int L, int R, int k) {
if (l > r) return;
int mid = l + (r-l) / 2;
int pos = 0, max = 0;
for (int i = L; i <= R; i++) {
int an = f[k-1][i] + (sum[mid] - sum[i]) * sum[i];
if (an > max) max = an, pos = i;
}
f[k][mid] = max; pre[k][mid] = pos;
solve(l, mid-1, L, pos, k), solve(mid+1, r, pos, R, k);
}
signed main() {
scanf("%lld%lld", &n, &m);
for (int i = 1; i <= n; i++) scanf("%lld", &sum[i]), sum[i] += sum[i-1];
for (int i = 1; i <= m; i++) solve(1, n, 1, n, i);
for (int now = n, k = m; now; now = pre[k][now], k--) ans[++ans[0]] = now;
std::reverse(ans+1, ans+1+ans[0]);
printf("%lld\n", f[m][n]);
for (int i = 1; i < ans[0]; i++) printf("%lld ", ans[i]);
return 0;
}