1 #include<bits/stdc++.h>

 2 using namespace std;

 3 const int N=5e5+10;

 4 int dp[N],s[N],q[N];

 5 int n,m;

 6

 7 int GetY(int k1,int k2){//求y得差值

 8     return dp[k2]+s[k2]*s[k2]-(dp[k1]+s[k1]*s[k1]);

 9 }

10

11 int GetX(int k1,int k2){//求x的差值

12     return s[k2]-s[k1];

13 }

14

15 int GetVal(int i,int j){//得到dp[i]的值

16     return dp[j]+(s[i]-s[j])*(s[i]-s[j])+m;

17 }

18

19 int main(){

20     while(~scanf("%d%d",&n,&m)){

21         s[0]=0;

22         dp[0]=0;

23         for(int i=1;i<=n;i++){

24             scanf("%d",&s[i]);

25             s[i]+=s[i-1];

26         }

27         int head=0,tail=0;

28         q[tail++]=0;//单调队列 ，该队列要维护斜率单增

29         for(int i=1;i<=n;i++){

30             while(head+1<tail && GetY(q[head],q[head+1])<=2*s[i]*GetX(q[head],q[head+1]))

31                 head++;//排除之前的不是最优的决策

32             dp[i]=GetVal(i,q[head]);

33

34             while(head+1<tail && GetY(q[tail-1],i)*GetX(q[tail-2],q[tail-1])<=GetY(q[tail-2],q[tail-1])*GetX(q[tail-1],i))

35                 tail--;//维护下凸包，不满足则删去

36             q[tail++]=i;

37         }

38         printf("%d\n",dp[n]);

39     }

40     return 0;

41 }