Police Operation

 Roy is helping the police department of his city in crime fighting. Today, they informed him about a new planned operation.

Think of the city as a  plane. The road along the -axis is very crime prone, because  criminals live there. No two criminals live at the same position.

To catch these criminals, the police department has to recruit some police officers and give each of them USD  as wages. A police officer can start his operation from any point , drive his car to point  in a straight line, and catch all the criminals who live on this way. The cost of fuel used by the officer's car is equal to the square of the euclidean distance between points  and  (Euclidean distance between points  and  equals to  ).

The police department asks Roy to plan this operation. So Roy has to tell them the number of officers to recruit and the routes these officers should take in order to catch all the criminals. Roy has to provide this information while minimizing the total expenses of this operation.

Find out the minimum amount of money required to complete the operation.

Input Format

The first line contains two integers  , number of criminals, and  , the cost of recruiting a police officer. The next line contains  space separated integers. The  integer indicates the position of the  criminal on -axis (in other words, if the  integer is , then location of the  criminal is ). The value of the positions are between  and  and are given in increasing order in the input.

Output Format

Print the minimum amount of money required to complete the operation.

Sample Input

5 10
1 4 5 6 9

Sample Output

34

Explanation

For the sample test case, police department recruits  officers who get paid . The first officer starts at point  and catches the criminal there. So he does not use any fuel. The second officer catches criminals at points ,  and . He burns fuel worth USD . The third officer catches the criminal at point . He also does not burn any fuel. The total money spent by the department is, .

Timelimits

Timelimits for this challenge are given here

SOLUTION:

#include <stdio.h>

#include <stdlib.h>

int get_i(double *a,int num,int size);

double med(double *a,int size);

double inter(long long m1,long long n1,long long m2,long long n2);

int a[2000000];

long long dp[2000000],m[2000000],n[2000000];

double aa[2000000];

int main(){

  int N,h,aa_size=0,i,j;

  long long t,tt;

  scanf("%d%d",&N,&h);

  for(i=0;i<N;i++)

    scanf("%d",&a[i]);

  for(i=0;i<N;i++){

    if(i)

      dp[i]=h+dp[i-1];

    else

      dp[i]=h;

    if(i && a[i]==a[i-1]){

      dp[i]=dp[i-1];

      continue;

    }

    if(aa_size){

      j=get_i(aa,a[i],aa_size-1);

      t=a[i]*(long long)a[i]+m[j]*a[i]+n[j];

      if(t<dp[i])

        dp[i]=t;

    }

    m[aa_size]=-2*a[i];

    if(i)

      n[aa_size]=a[i]*(long long)a[i]+h+dp[i-1];

    else

      n[aa_size]=a[i]*(long long)a[i]+h;

    j=++aa_size;

    while(aa_size>2){

      if(inter(m[aa_size-3],n[aa_size-3],m[j-1],n[j-1])>aa[aa_size-3])

        break;

      aa_size--;

    }

    tt=m[j-1];

    m[j-1]=m[aa_size-1];

    m[aa_size-1]=tt;

    tt=n[j-1];

    n[j-1]=n[aa_size-1];

    n[aa_size-1]=tt;

    if(aa_size>1)

      aa[aa_size-2]=inter(m[aa_size-2],n[aa_size-2],m[aa_size-1],n[aa_size-1]);

  }

  printf("%lld",dp[N-1]);

  return 0;

}

int get_i(double *a,int num,int size){

  if(size==0)

    return 0;

  if(num>med(a,size))

    return get_i(&a[(size+1)>>1],num,size>>1)+((size+1)>>1);

  else

    return get_i(a,num,(size-1)>>1);

}

double med(double *a,int size){

  return a[(size-1)>>1];

}

double inter(long long m1,long long n1,long long m2,long long n2){

  return (n2-n1)/(double)(m1-m2);

}