决策单调性做法，斜率优化做法问题可能也是这个。

在判断最优决策点时取最靠左的决策点，不然如果答案是 0 的话可能在0也能取到最优决策点不符合题意。

void solve(int l, int r, int L, int R, int k) {
	if (l > r) return;
	int mid = (l + r) / 2, pos = 0;
	ll maxv = 0;
	for (int i = L; i < mid && i <= R; i ++) {
		ll v = f[k - 1][i] + 1ll * s[i] * (s[mid] - s[i]);
		if (v >= maxv) maxv = v, pos = i;
	}
	f[k][mid] = maxv, g[k][mid] = pos;
	solve(l, mid - 1, L, pos, k), solve(mid + 1, r, pos, R, k);
}

就是代码中的 v >= maxv 不要写成 v > maxv

附第三组数据

input

2 1
0 123

output

0
1