BNUOJ 26224 Covered Walkway

 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 INF 0x3f3f3f3f
15 using namespace std;
16 const int maxn = 1000100;
17 LL n,c,d[maxn],dp[maxn];
18 int q[maxn],head,tail;
19 LL G(int k,int j){
20     return dp[j] + d[j+1]*d[j+1] - (dp[k]+d[k+1]*d[k+1]);
21 }
22 LL S(int k,int j){
23     return (d[j+1]-d[k+1]);
24 }
25 int main(){
26     int i,j;
27     while(scanf("%I64d %I64d",&n,&c),(n||c)){
28         for(i = 1; i <= n; i++)
29             scanf("%I64d",d+i);
30         dp[0] = q[0] = 0;
31         head = tail = 0;
32         for(i = 1; i <= n; i++){
33             while(head < tail && G(q[head],q[head+1]) <= 2*d[i]*S(q[head],q[head+1])) head++;
34             dp[i] = dp[q[head]] + (d[i]-d[q[head]+1])*(d[i]-d[q[head]+1])+c;
35             while(head < tail && G(q[tail-1],q[tail])*S(q[tail],i) >= G(q[tail],i)*S(q[tail-1],q[tail])) tail--;
36             q[++tail] = i;
37         }
38         printf("%I64d\n",dp[n]);
39     }
40     return 0;
41 }