### Brief description:

略。）

### Analysis:

老套路。。雖然題目保證 32-int。。。但是實際還是有一些危險的（？）。

。全程 LL 居然會 TLE。=_=）

//}/* .................................................................................................................................. */ const int N = int(1e4) + 9; int _f[2][N], *f = _f[0], *ff = _f[1]; int A[N]; int q[N], cz, op; int n, m; #define k (-2*A[i]) #define x(j) (A[j+1]) #define y(j) (ff[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 Rush{ RD(n, m); REP_1(i, n) RD(A[i]); sort(A+1, A+n+1); REP_1(i, n) f[i] = sqr(A[i] - A[1]); DO(m-1){ swap(f, ff); cz = 0, op = -1; REP_1(i, n){ while (cz < op && dett(q[op-1], q[op], i) <= 0) --op; q[++op] = i; while (cz < op && eval(q[cz]) >= eval(q[cz+1])) ++cz; f[i] = sqr(A[i]) + eval(q[cz]); } } OT(f[n]); } }

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