这篇题解主要说一下细节问题，即题解和讨论区中都提到的斜率优化时要不要加等于号这件事。

这题的数据比较水，所以稍微改改就过了，这里说一下结论：如果一个位置的 dp 值可以从多个位置转移过来，选择其中转移次数最多的（注：我的写法是二分时若转移次数大于等于 $m$，则接受这个答案；如果有人写的和我相反，就选择转移次数最少的）。

具体的原因就是，我们二分的是斜率，而这个凸函数可能存在连续一段斜率相同的，设为 $[l,r]$，若 $l<m<r$，我们不对转移次数进行限制，就有可能取到 $l$，从而舍弃这个答案。

知道这点后代码就极其好写了，不懂的看代码就行了。

#include<cstdio>
int n,m,g[100010],s[100010],q[100010];
long long f[100010],h[100010];
bool check(long long mid){
	int hd=0,tl=0;
	for(int i=1;i<=n;i++){
		while(hd<tl&&((h[q[hd+1]]-h[q[hd]])<2ll*s[i]*(s[q[hd+1]]-s[q[hd]])||((h[q[hd+1]]-h[q[hd]])==2ll*s[i]*(s[q[hd+1]]-s[q[hd]]&&g[q[hd+1]]>=g[q[hd]]))))++hd;
		f[i]=f[q[hd]]+(s[i]-s[q[hd]]+1ll)*(s[i]-s[q[hd]]+1ll)-mid;
		g[i]=g[q[hd]]+1;
		h[i]=f[i]-2*s[i]+1ll*s[i]*s[i];
		while(hd<tl&&((h[q[tl]]-h[q[tl-1]])*(s[i]-s[q[tl]])>(h[i]-h[q[tl]])*(s[q[tl]]-s[q[tl-1]])||((h[q[tl]]-h[q[tl-1]])*(s[i]-s[q[tl]])==(h[i]-h[q[tl]])*(s[q[tl]]-s[q[tl-1]])&&g[i]>=g[q[tl]])))--tl;
		q[++tl]=i;
	}
	return g[n]>=m;
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1,x;i<=n;i++)scanf("%d",&x),s[i]=s[i-1]+x;
	long long l=-1e18,r=0,ans=0;
	while(l<=r){
		long long mid=(l+r)/2;
		if(check(mid)) ans=mid,r=mid-1;
		else l=mid+1;
	}
	check(ans);
	printf("%lld\n",f[n]+m*ans);
	return 0;
}