HDU 3507 Print Article

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cmath>
 5 #include <algorithm>
 6 #include <climits>
 7 #include <vector>
 8 #include <queue>
 9 #include <cstdlib>
10 #include <string>
11 #include <set>
12 #include <stack>
13 #define LL long long
14 #define pii pair<int,int>
15 #define INF 0x3f3f3f3f
16 using namespace std;
17 const int maxn = 500010;
18 LL sum[maxn],dp[maxn];
19 int n,m,q[maxn],head,tail;
20 LL G(int j,int k){
21     LL a = dp[j]+sum[j]*sum[j];
22     LL b = dp[k]+sum[k]*sum[k];
23     return a-b;
24 }
25 LL S(int j,int k){
26     return (sum[j] - sum[k])*2;
27 }
28 int main() {
29     int i;
30     while(~scanf("%d %d",&n,&m)){
31         sum[0] = 0;
32         for(i = 1; i <= n; i++){
33             scanf("%I64d",sum+i);
34             sum[i] += sum[i-1];
35         }
36         q[0] = dp[0] = head = tail = 0;
37         for(i = 1; i <= n; i++){
38             while(head < tail && G(q[head+1],q[head]) <= sum[i]*S(q[head+1],q[head])) ++head;
39             dp[i] = dp[q[head]] + (sum[i] - sum[q[head]])*(sum[i] - sum[q[head]])+m;
40             while(head < tail && G(q[tail-1],q[tail])*S(q[tail],i) >= G(q[tail],i)*S(q[tail-1],q[tail])) --tail;
41             q[++tail] = i;
42         }
43         printf("%I64d\n",dp[n]);
44     }
45     return 0;
46 }