BZOJ/1911.c

   1 /**************************************************************
   2     Problem: 1911
   3     User: dennisyang
   4     Language: C
   5     Result: Accepted
   6     Time:1708 ms
   7     Memory:20288 kb
   8 ****************************************************************/
   9
  10 /*
  11 dp[i] = max{dp[j-1] + a*sqr(sum[i]-sum[j-1])+b*(sum[i]-sum[j-1])+c}
  12
  13 dp[k-1]+a*sqr(sum[i]-sum[k-1])+b*(sum[i]-sum[k-1]) > dp[j-1]+a*sqr(sum[i]-sum[j-1])+b*(sum[i]-sum[j-1])
  14 dp[k-1] + a*(-2*sum[i]*sum[k-1]+sqr(sum[k-1])) + b*(-sum[k-1]) > dp[j-1] + a*(-2*sum[i]*sum[j-1]+sqr(sum[j-1])) + b*(-sum[j-1])
  15
  16 (dp[k-1]+a*sqr(sum[k-1])-b*sum[k-1]) - (dp[j-1]+a*sqr(sum[j-1])-b*sum[j-1]) > 2a*sum[i]*(sum[k-1]-sum[j-1])
  17
  18 y(k) = dp[k-1]+a*sqr(sum[k-1])-b*sum[k-1]
  19 x(k) = 2a*sum[k-1]
  20
  21 y(k)-y(j) > sum[i]*(x(k)-x(j))
  22
  23 j<k (x(j) > x(k))
  24     slope < sum[i]
  25 j>k (x(j) < x(k))
  26     slope > sum[i]
  27 */
  28 #include <stdio.h>
  29
  30 #define sqr(x) ((x)*(x))
  31 #define cal(x) (a*sqr(x)+b*(x)+c)
  32 #define maxn 1000001
  33
  34 typedef long long int64;
  35
  36 int n,queue[maxn];
  37 int64 a,b,c,sum[maxn],dp[maxn];
  38
  39 inline double y(int k) {
  40     return dp[k-1] + a*sqr(sum[k-1]) - b*sum[k-1];
  41 }
  42
  43 inline double x(int k) {
  44     return 2*a*sum[k-1];
  45 }
  46
  47 inline double slope(int p, int q) {
  48     return (y(p)-y(q)) / (x(p)-x(q));
  49 }
  50
  51 int main() {
  52     scanf("%d",&n);
  53     scanf("%lld%lld%lld",&a,&b,&c);
  54     int i;
  55     for (i=1; i<=n; ++i) scanf("%lld",sum+i);
  56     for (i=1; i<=n; ++i) sum[i] += sum[i-1];
  57     int *qf = &queue[1], *qr = &queue[0];
  58     for (i=1; i<=n; ++i) {
  59         while (qf < qr && slope(*(qr-1),*qr) > slope(*qr,i)) --qr;
  60         *++qr = i;
  61         while (qf < qr && slope(*qf,*(qf+1)) < sum[i]) ++qf;
  62         dp[i] = dp[*qf - 1] + cal(sum[i] - sum[*qf - 1]);
  63     }
  64     printf("%lld\n",dp[n]);
  65     return 0;
  66 }