# 某島

… : "…アッカリ～ン . .. . " .. .
October 2, 2014

## HDU 3507. Print Article

### Analysis:

（又沒 Ci 的數據範圍。）

```
//}/* .................................................................................................................................. */

const int N = int(5e5) + 9;
LL f[N], C[N]; int q[N], cz, op;
int n, m;

#define k (-2*C[i])
#define x(j) (C[j])
#define y(j) (f[j] + sqr(x(j)))
#define eval(j) (k*x(j) + y(j))

LL det(LL x1, LL y1, LL x2, LL y2){
return x1*y2 - x2*y1;
}
int dett(int p0, int p1, int p2){
LL t = det(x(p1)-x(p0), y(p1)-y(p0), x(p2)-x(p0), y(p2)-y(p0));
return t < 0 ? -1 : t > 0;
}

int main(){

#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
#endif

while (~scanf("%d %d", &n, &m)){

REP_1(i, n) C[i] = C[i-1] + RD();

cz = 0, op = 0; REP_1(i, n){
while (cz < op && eval(q[cz]) >= eval(q[cz+1])) ++cz; f[i] = m + sqr(C[i]) + eval(q[cz]);
while (cz < op && dett(q[op-1], q[op], i) <= 0) --op; q[++op] = i;
}

OT(f[n]);
}
}
```

http://acm.hust.edu.cn/vjudge/problem/viewSource.action?id=2801203