[HOJ] 236 - Commando

#include<stdio.h>
#define N 1000005
int Q[N]={0};
long long int S[N]={0},dp[N]={0},a,b,c;
double K(int x,int y){
    return double(dp[x]-dp[y]+a*(S[x]*S[x]-S[y]*S[y]))/double(S[x]-S[y]);
}
int main(){
    int n,i,l=1,r=1;
    scanf("%d%lld%lld%lld",&n,&a,&b,&c);
    for(i=1;i<=n;i++){
        scanf("%lld",&S[i]);
        S[i]+=S[i-1];
    }
    for(i=1;i<=n;i++){
        while(l<r && K(Q[l],Q[l+1])>=double(2*a*S[i])) l++;
        long long int x=S[i]-S[Q[l]];
        dp[i]=dp[Q[l]]+a*x*x+c;
        while(l<r && K(Q[r-1],Q[r])<=K(Q[r],i)) r--;
        Q[++r]=i;
    }
    printf("%lld\n",dp[n]+S[n]*b);
}