fork download
copy 
  1. import java.io.*;
  2. import java.util.*;
  3. class CLDSIN{
  4.     static class Line{
  5.         long m, c;
  6.         Line(long m, long c){
  7.             this.m = m;
  8.             this.c = c;
  9.         }
  10.  
  11.         long valueAt(long x){
  12.             return m*x+c;
  13.         }
  14.     }
  15.  
  16.     public static void main(String args[])throws Exception{
  17.         Reader re = new Reader(System.in);
  18.         int N = re.nextInt();
  19.         int R = re.nextInt();
  20.         long P[] = new long[N+1];
  21.         for(int i=1; i<=N; i++)
  22.             P[i] = re.nextInt();
  23.         long ans = work(P, R);
  24.         System.out.println(ans);
  25.     }
  26.  
  27.     static long work(long[] P, int R){
  28.         int N = P.length-1;
  29.         long dp[] = new long[N+1];
  30.         LinkedList<Line> dq = new LinkedList<>();
  31.         dq.add(new Line(-2*P[1], sqr(P[1])));
  32.         for(int i=1; i<=N; i++){
  33.             while(dq.size()>1){
  34.                 if(dq.get(0).valueAt(P[i]) < dq.get(1).valueAt(P[i]))
  35.                     break;
  36.                 dq.removeFirst();
  37.             }
  38.             dp[i] = R+sqr(P[i])+dq.peek().valueAt(P[i]);
  39.             if(i<N){
  40.                 Line l3 = new Line(-2*P[i+1], sqr(P[i+1])+dp[i]);
  41.                 while(dq.size()>1){
  42.                     Line l1 = dq.get(dq.size()-2);
  43.                     Line l2 = dq.get(dq.size()-1);
  44.                     double l1l3 = 1.0*(l1.m-l3.m)/(l3.c-l1.c);
  45.                     double l2l3 = 1.0*(l2.m-l3.m)/(l3.c-l2.c);
  46.                     if(l1l3>l2l3)
  47.                         break;
  48.                     dq.removeLast();
  49.                 }
  50.                 dq.addLast(l3);
  51.             }
  52.         }
  53.         return dp[N];
  54.     }
  55.  
  56.     static long sqr(long x){
  57.         return x*x;
  58.     }
  59. }
  60.  
  61. class Reader{
  62.     BufferedReader br;
  63.     StringTokenizer st;
  64.     Reader(InputStream in) throws Exception{
  65.         br = new BufferedReader(new InputStreamReader(in));
  66.         st = new StringTokenizer("");
  67.     }
  68.  
  69.     String next() throws Exception{
  70.         while(!st.hasMoreTokens())
  71.             st = new StringTokenizer(br.readLine());
  72.         return st.nextToken();
  73.     }
  74.  
  75.     int nextInt() throws Exception{
  76.         return Integer.parseInt(next());
  77.     }
  78. }
  79.  
Success #stdin #stdout 0.09s 320576KB
comments (?)
stdin
copy 
2 10
1 2
stdout
copy 
11
https://ideone.com/3enrxS
language:
Java (HotSpot 12)
created:
8 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!