设 $f[i]$ 表示前$i$个数划分完后的最小代价

$s[i]$ 表示前$i$ 个数的和

$f[i]=min(f[j]+(s[i]-s[j])^2+C)$

这个是典型的一维动态规划，而且它的$w(i,j)$是关于$s[i]*s[j]$的，因此我们想到要用斜率优化

$w(i,j) = (s[i]-s[j])^2+C$

然后我们容易证明

$w(i,j)+w(i+1,j+1) <= w(i+1,j) + w(i,j+1)$

则它满足四边形不等式

因此这个递推式子有决策单调性

然后我们化简一下式子

$f[i]-s[i]*s[i]-c=f[j]-2*s[j]*s[i]+s[j]*s[j]$

我们如果要用斜率优化，我们要满足$k$为一个关于$i$的东西且它得和一个关于$j$的东西相乘，$x$为一个关于$j$的东西且它得和一个关于$i$的东西相乘，$b$为一个关于$i$的东西，$y$为一个关于$j$的东西

那么我们可以得出

$x = s[j]$ $y = f[j] + s[j]*s[j]$ $k = 2*s[i]$ $b = f[i]-s[i]*s[i]-c$

这样我们的问题就变为如何让这个一次函数的截距最小

我们设$k < j < i$ 且$j$比$k$优

即$f[j]-2*s[j]*s[i]+s[j]*s[j]<f[k]-2*s[k]*s[i]+s[k]*s[k]$

化简可得$Y(j)-Y(k)/X(j)-X(k)<=2*s[i]$

那么只要满足这个式子就可以保证$j$比$k$优

假设有三个点$P(j1)$ $P(j2)$ $P(j3)$

$k1$为$P(j1)$ $P(j2)$的斜率

$k2$为$P(j3)$ $P(j2)$的斜率

假设$k2 < k1$ $k0$为$2*s[i]$

$k0 < k2 < k1$ $j1$优于$j2$优于$j3$ $k2 <= k0 < k1$ $j1$,$j3$优于$j2$ $k2 < k1 <= k0$ $j3$优于$j2$优于$j1$

可以发现这三个情况$j2$都是劣的

所以我们可以把它扔掉

所以我们要维护的点是在一个下凸包

然后他的斜率是单增的

然后我们最优的点就是最小的那个满足$k<=2s[i]$,然后他又有决策单调性

所以我们可以用一个单调队列，队头用$k<=2s[i]$去判，如果不行就扔，队尾维护一个下凸包就好

然后这个题就做完了

#include <bits/stdc++.h>
using namespace std;

const long long N = 5e5 + 10;

long long n, c, a[N], s[N], f[N], st[N], h, t;

void read(){
	for(long long i = 1;i <= n; i++){
		cin >> a[i];
		s[i] = s[i-1] + a[i]; 
	}
}

double X(long long i){
	return s[i];
}

double Y(long long i){
	return f[i] + s[i] * s[i];
}

double k(long long a,long long b){
	if(X(a)-X(b) == 0) return 1e18;
	return (Y(a)-Y(b))/(X(a)-X(b));
}

void compute(){
	memset(f,0,sizeof f);
	memset(st,0,sizeof st);
	h = t = 0;
	st[t++] = 0;
	for(long long i = 1;i <= n; i++){
		while(t - h > 1 && k(st[h],st[h+1]) <= s[i] * 2) h++;
		f[i] = f[st[h]] + (s[st[h]] - s[i]) * (s[st[h]] - s[i]) + c;
		while(t - h > 1 && k(st[t-1],st[t-2]) >= k(st[t-1],i)) t--;
		st[t++] = i;
	}
	cout << f[n] << '\n';
}

int main(){
	while(cin >> n >> c){
		read();
		compute();
	}
	return 0;
}