斜率优化dp。
容易写出dp[i]=max{dp[j]+a * (s[i]-s[j])^2+b * (s[i]-s[j])+c}
变形得到dp[j]+a * s[j]^2-b * s[j]=2 * a * s[i] * s[j]+dp[i]-b * s[i]-c
令y=dp[j]+a * s[j]^2-b * s[j]
k=2 * a * s[i]
b=dp[i]-b * s[i]-c
问题就变为给定直线的斜率和一些点，求使直线的截距最大的点。
因为斜率单调减小，所以用双端队列维护上凸壳，队头所有斜率大于当前斜率的之后再也不会用到，可以出队。队尾不满足上凸的也要弹出。
#include<cstdio>
#include<cstring>
#define LL long long
LL dp[1000010],que[1000010],a[1000010],s[1000010];
double f[1000010],g[1000010];
double tj(int p,int q)
{return (f[q]-f[p])/((double)s[q]-s[p]);
}
int main()
{int i,j,k,m,n,p,q,x,y,z,A,B,C,hd=1,tl=1;scanf("%d%d%d%d",&n,&A,&B,&C);for (i=1;i<=n;i++){scanf("%lld",&a[i]);s[i]=s[i-1]+a[i];g[i]=2*A*s[i];}for (i=1;i<=n;i++){while (hd<tl&&tj(que[hd],que[hd+1])>=g[i]) hd++;dp[i]=dp[que[hd]]+(LL)A*(s[i]-s[que[hd]])*(s[i]-s[que[hd]])+(LL)B*(s[i]-s[que[hd]])+(LL)C;f[i]=dp[i]+(LL)A*s[i]*s[i]-(LL)B*s[i];while (hd<tl&&tj(que[tl-1],que[tl])<=tj(que[tl],i)) tl--;que[++tl]=i;}printf("%lld\n",dp[n]);
}