HackerRank Police Operation Problem 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);
}

#include <algorithm>
#include <cstdio>
using namespace std;

#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define REP(i, n) for (int i = 0; i < (n); i++)
#define REP1(i, n) for (int i = 1; i <= (n); i++)
#define ROF(i, a, b) for (int i = (b); --i >= (a); )
#define P(x) ((x)*(x))
#define F(x,y) (P(a[(y)+1])-P(a[(x)+1])+dp[y]-dp[x])

int ri()
{
  int x;
  scanf("%d", &x);
  return x;
}

const int N = 2000000;
int q[N+1];
long a[N+1], dp[N+1];

int main()
{
  int n = ri(), x = ri(), *fr = q, *re = q+1;
  REP1(i, n)
    a[i] = ri();
  n = unique(a+1, a+n+1) - (a+1);
  REP1(i, n) {
    while (fr+1 < re && 2*a[i]*(a[fr[1]+1]-a[*fr+1]) > F(*fr, fr[1]))
      fr++;
    dp[i] = dp[*fr]+P(a[i]-a[*fr+1])+x;
    if (i < n) {
      while (fr <= re-2 && F(re[-2], re[-1]) / (a[re[-1]+1]-a[re[-2]+1]) > F(re[-1], i) / (a[i+1]-a[re[-1]+1]))
        re--;
      *re++ = i;
    }
  }
  printf("%ld\n", dp[n]);
}

using System;
using System.Collections;
using System.Collections.Generic;
using System.IO;
using System.Linq;

class Solution {

    static long policeOperation(long h, int[] crims)
    {
        if (h == 0 || crims == null || crims.Length == 0)
            return 0;
        else if (h == 1)
            return crims.Length;
        if (crims.Length == 1)
            return h;
        //Array.Sort(crims);
        
        var cost = new long[crims.Length + 1];
        var next = new KeyValuePair<long,long>[crims.Length];
        int s = 0; 
        int c = 0;

        cost[0] = 0;
        for (int i = 0; i < crims.Length; ++i)
        {
            long pos = crims[i];
            long nextcost = h + pos * pos + cost[i];
            while (
                s > 1
                &&
                (nextcost - next[s - 2].Value) * (next[s - 1].Key - next[s - 2].Key)
                <=
                (next[s - 1].Value - next[s - 2].Value) * (pos - next[s - 2].Key)
            )
            {
                s--;
                c--;
                if (c < 0) c = 0;
            }
            next[s] = new KeyValuePair<long,long>(pos, nextcost);

            s++;

            while (
                c < s - 1
                &&
                    next[c + 1].Value - 2 * next[c + 1].Key * pos < next[c].Value - 2 * next[c].Key * pos
            )
                c++;

            cost[i + 1] = next[c].Value + pos * pos - 2 * next[c].Key * pos;
        }

        return cost[cost.Length - 1];
    }

    static void Main(string[] args) {
        TextWriter textWriter = new StreamWriter(@System.Environment.GetEnvironmentVariable("OUTPUT_PATH"), true);

        string[] nh = Console.ReadLine().Split(' ');
        int n = Convert.ToInt32(nh[0]);
        int h = Convert.ToInt32(nh[1]);
        if(n == 0 || h == 0)
        {
            textWriter.WriteLine("0");
        }
        else
        {
            int[] criminals = Array.ConvertAll(Console.ReadLine().Split(' '), criminalsTemp => Convert.ToInt32(criminalsTemp));
            long result = policeOperation(h, criminals);
            textWriter.WriteLine(result);
        }  

        textWriter.Flush();
        textWriter.Close();
    }
}

import java.io.*;
import java.math.*;
import java.text.*;
import java.util.*;
import java.util.regex.*;

public class Solution {

  static long square(long x) {
    return x * x; 
  }
  static long[] dp;
  static int[] criminals;

  static long distance(int x, int y) {
    return (square(criminals[y]) - square(criminals[x]) + dp[y] - dp[x]);
  }
  
  static long policeOperation(int n, int h, int[] criminals) {
    dp = new long[n + 1];
    int[] q = new int[n + 1];
    int fr = 0;
    int re = 1;
    for (int i = 1; i <= n; i++) {
      while (fr + 1 < re 
          && 2 * (long)criminals[i-1] * (criminals[q[fr + 1]] - criminals[q[fr]]) > distance(q[fr], q[fr + 1])) {
        fr++;
      }
      dp[i] = dp[q[fr]] + square(criminals[i-1] - criminals[q[fr]]) + h;
      if (i < n) {
        while (fr <= re - 2 
            && distance(q[re - 2], q[re - 1]) / (criminals[q[re - 1]] - criminals[q[re - 2]]) >
        distance(q[re - 1], i) / (criminals[i] - criminals[q[re - 1]])) {
          re--;
        }
        q[re] = i;
        re++;
      }
    }
    return dp[n];
  }

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

    StringTokenizer st = new StringTokenizer(br.readLine());
    int n = Integer.parseInt(st.nextToken());
    int h = Integer.parseInt(st.nextToken());

    long result = 0;
    if (h > 0 && n > 0) {
      criminals = new int[n];
      int index = 0;

      st = new StringTokenizer(br.readLine());
      for (int i = 0; i < n; i++) {
        int item = Integer.parseInt(st.nextToken());
        if (index == 0 || item > criminals[index]) {
          criminals[index++] = item;
        }
      }
      result = policeOperation(index, h, criminals);
    }

    bw.write(String.valueOf(result));
    bw.newLine();

    br.close();
    bw.close();
  }
}

#!/bin/python3

import os
import sys

#
# Complete the policeOperation function below.
#
def cross(f, g):
    return (g[1]-f[1])/(f[0]-g[0])

def policeOperation(h, criminals):
    n = len(criminals)
    dp = 0
    stack = []
    fpos = 0
    for i in range(0,n):
        f = [-2*criminals[i],criminals[i]*criminals[i] + dp,0]
        
        while len(stack) > 0:
            f[2] = cross(stack[-1], f)
            if stack[-1][2] < f[2]:
                break
            stack.pop()
            if len(stack) == fpos:
                fpos -= 1

        stack.append(f)
        x = criminals[i];
        while fpos+1 < len(stack) and stack[fpos+1][2] < x: fpos += 1
        dp = stack[fpos][0] * x + stack[fpos][1] + h + x*x;   

    return dp




if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    nh = input().split()

    n = int(nh[0])

    h = int(nh[1])
    result = 0
    if n != 0:
        criminals = list(map(int, input().rstrip().split()))
        result = policeOperation(h, criminals)

    fptr.write(str(result) + '\n')

    fptr.close()