[APIO 2010] 特别行动队

#includeusing namespace std;
const int N = 1000010;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;

int n , l , r;
ll a , b , c;
int q[N];
ll f[N] , sum[N] , X[N] , Y[N];

template  inline void chkmax(T &x , T y) { x = max(x , y); }
template  inline void chkmin(T &x , T y) { x = min(x , y); }
template  inline void read(T &x)
{
    T f = 1; x = 0;
    char c = getchar();
    for (; !isdigit(c); c = getchar()) if (c == ‘-‘) f = -f;
    for (; isdigit(c); c = getchar()) x = (x 3) + (x 1) + c - ‘0‘;
    x *= f;
}

int main()
{
        
        read(n);
        read(a); read(b); read(c);
        for (int i = 1; i )
        {
                int x;
                read(x);
                sum[i] = sum[i - 1] + x;
                X[i] = sum[i];
        }
        f[q[l = r = 1] = 0] = 0;
        for (int i = 1; i )
        {
                while (l 1]] - Y[q[l]] >= (2 * a * sum[i] + b) * (X[q[l + 1]] - X[q[l]])) ++l;
                f[i] = Y[q[l]] - X[q[l]] * (2 * a * sum[i] + b) + a * sum[i] * sum[i] + b * sum[i] + c;
                Y[i] = f[i] + a * sum[i] * sum[i];
                while (l 1]]) >= (Y[q[r]] - Y[q[r - 1]]) * (X[i] - X[q[r]])) --r;
                q[++r] = i;        
        }
        printf("%lld\n" , f[n]);
        
        return 0;
    
}