# [BZOJ1911]&&[Apio2010] 特别行动队

## 样例输入 SampleInput

500
-1 100 -1000
12 58 12 11 22 59 41 54 5 16 87 74 88 55 21 50 16 79 94 10 96 90 22 12 60 6 78 96 59 8 52 3 51 63 59 96 90 56 57 25 38 62 89 47 12 77 3 14 62 75 65 76 66 18 29 4 54 62 41 47 22 50 73 30 43 58 91 69 33 68 59 23 82 79 94 34 12 63 17 81 49 7 10 13 51 91 86 44 31 82 59 92 73 30 31 23 48 54 97 89 21 69 4 74 26 95 47 82 1 1 92 55 22 72 92 50 25 66 21 76 83 60 76 30 16 63 41 90 58 66 57 48 8 28 24 46 25 70 55 67 73 98 96 50 88 37 71 6 86 15 35 24 95 25 25 17 72 84 60 24 65 47 2 99 28 60 86 17 98 35 79 62 5 16 40 32 18 8 92 65 40 1 36 25 53 45 98 5 39 44 52 56 25 85 29 21 35 39 71 45 31 96 7 66 58 65 41 4 90 55 63 3 17 6 3 58 74 56 10 43 70 52 88 66 26 71 18 22 28 55 31 33 7 87 14 8 70 82 90 19 71 91 75 61 24 28 60 48 78 97 98 38 66 68 44 79 25 3 12 7 22 17 89 94 78 17 100 42 35 19 20 72 1 60 85 7 17 24 5 97 14 14 94 26 38 4 42 26 40 7 7 70 83 25 13 55 92 66 27 86 91 16 2 3 16 46 32 99 67 34 39 55 28 17 80 40 85 28 39 24 57 56 60 74 90 95 44 84 96 13 40 19 28 64 17 33 84 100 53 63 32 50 41 46 38 23 7 71 89 91 38 95 94 50 83 72 75 31 98 29 41 76 14 82 81 13 53 56 5 48 39 50 15 87 61 40 54 84 37 43 41 66 44 9 69 33 11 78 46 20 26 19 68 9 10 42 6 57 69 51 47 12 3 73 68 11 91 87 90 55 99 68 88 13 72 81 96 13 41 71 67 76 61 57 58 69 51 31 34 85 34 67 74 89 53 6 28 8 32 47 88 30 40 27 24 76 12 68 25 5 20 56 46 93 38 60 87 16 79 38 87 68 91 38 86 43 84 52 9 83 24 58 94 67 1 23 88 55 92 9 71 90 93 99 8 87 34 86 99 13 98 50 64 32 89 71 12 9 17 8

## 样例输出 SampleOutput

362631

BZOJ 1911

$f[i]=Max \lbrace f[j]+a*(\sum_{k=j+1}^{i}x_{k})^{2}+b*\sum_{k=j+1}^{i}x_{k}+c \rbrace$

$f[i]=Max \lbrace f[j]+a*(sum[i]-sum[j])^{2}+b*(sum[i]-sum[j])+c \rbrace$

$k<j<i$ 且对于 $i$ 而言 $f[j]$ 优于 $f[k]$，则

$f[j]+a*(sum[i]-sum[j])^{2}+b*(sum[i]-sum[j])+c \\\\ >f[k]+a*(sum[i]-sum[k])^{2}+b*(sum[i]-sum[k])+c$

$\frac{(f[j]+a*sum[j]^{2}-b*sum[j])-(f[k]+a*sum[k]^{2}-b*sum[k])} {sum[j]-sum[k]}>2*a*sum[i]$

#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
#define ll long long
const ll maxn=1000005;
ll i,j,t,n,m,l,r,k,z,y;
ll a,b,c;
ll x[maxn],sum[maxn],f[maxn],q[maxn];
inline ll fracup(ll x,ll y)
{
return (f[x]+a*sum[x]*sum[x]-b*sum[x])-(f[y]+a*sum[y]*sum[y]-b*sum[y]);
}
inline ll fracdown(ll x,ll y)
{
return sum[x]-sum[y];
}
int main()
{
scanf("%lld",&n);
scanf("%lld%lld%lld",&a,&b,&c);
sum[0]=0;
for (i=1;i<=n;i++) scanf("%lld",&x[i]),sum[i]=sum[i-1]+x[i];
}