今天骟老师讲斜率优化，自己不会实在惭愧，A一道模板题感受一下 发现比去年这时候好多了，没多少时间就懂了
//By Richard
#include <queue>
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <ctime>
#define rep(x,y,z) for (int x=(y);(x)<=(z);(x)++)
#define per(x,y,z) for (int x=(y);(x)>=(z);(x)--)
#define log2(x) (31-__builtin_clz(x))
#define mod (int)(1e9+7)
#define inf 0x3f3f3f3f
#define cls(x) memset(x,0,sizeof(x))
#ifdef DEBUG
#define debugdo(X) X
#define debugndo(X)
#define debugout(X) cout<<(#X)<<"="<<(X)<<endl
#else
#define debugdo(X)
#define debugndo(X) X
#define debugout(X)
#endif // debug
#ifdef ONLINE_JUDGE
#define debugdo(X)
#define debugndo(X)
#define debugout(X)
#endif
#define putarray(x,n) rep(iiii,1,n) printf("%d ",x[iiii])
#define mp make_pair
using namespace std;
typedef pair<int,int> pairs;
typedef long long LL;
/////////////////////read3.0////////////////////////////////////
template <typename T>
inline void read(T &x){char ch;x=0;bool flag=false;ch=getchar();while (ch>'9'||ch<'0') {ch=getchar();if (ch=='-') flag=true;}while ((ch<='9'&&ch>='0')){x=x*10+ch-'0';ch=getchar();}if (flag) x*=-1;}
template <typename T>
inline void read(T &x,T &y){read(x);read(y);}
/////////////////variables&functions////////////////////
inline int sqr(const int &x){return x*x;}
const int maxn=555555;
int n,m,a[maxn],sum[maxn],f[maxn],q[maxn],x;
int X(int x)
{
return f[x]+sum[x]*sum[x];
}
int Y(int x,int y)
{
return (sum[x]-sum[y])<<1;
}
int main()
{
while (scanf("%d%d",&n,&m)!=EOF)
{
int head=0,tail=1;//head to tail-1
q[0]=0;
rep(i,1,n)
{
read(x);
sum[i]=x+sum[i-1];
while (head+1<tail&&(X(q[head+1])-X(q[head])<=Y(q[head+1],q[head])*sum[i])) ++head;
f[i]=(sum[i]-sum[q[head]])*(sum[i]-sum[q[head]])+m+f[q[head]];
while (head+1<tail&&(Y(i,q[tail-1])*(X(q[tail-1])-X(q[tail-2]))>=Y(q[tail-1],q[tail-2])*(X(i)-X(q[tail-1])))) --tail;
q[tail++]=i;
}
printf("%d\n",f[n]);
}
return 0;
}