Problem:
 Score : 100 points    Problem Statement There are N stones, numbered 1, 2, \ldots, N .
For each i ( 1 \leq i \leq N ), the height of Stone i is h_i .
Here, h_1 < h_2 < \cdots < h_N holds.  There is a frog who is initially on Stone 1 .
He will repeat the following action some number of times to reach Stone N :   If the frog is currently on Stone i , jump to one of the following: Stone i + 1, i + 2, \ldots, N . Here, a cost of (h_j - h_i)^2 + C is incurred, where j is the stone to land on.   Find the minimum possible total cost incurred before the frog reaches Stone N .      Constraints  All values in input are integers.  2 \leq N \leq 2 \times 10^5  1 \leq C \leq 10^{12}  1 \leq h_1 < h_2 < \cdots < h_N \leq 10^6         Input Input is given from Standard Input in the following format:  N  C  h_1  h_2  \ldots  h_N       Output Print the minimum possible total cost incurred.        Sample Input 1 5 6
1 2 3 4 5      Sample Output 1 20  If we follow the path 1 → 3 → 5 , the total cost incurred would be ((3 - 1)^2 + 6) + ((5 - 3)^2 + 6) = 20 .       Sample Input 2 2 1000000000000
500000 1000000      Sample Output 2 1250000000000  The answer may not fit into a 32-bit integer type.       Sample Input 3 8 5
1 3 4 5 10 11 12 13      Sample Output 3 62  If we follow the path 1 → 2 → 4 → 5 → 8 , the total cost incurred would be ((3 - 1)^2 + 5) + ((5 - 3)^2 + 5) + ((10 - 5)^2 + 5) + ((13 - 10)^2 + 5) = 62 .

Solution (Python):
def nasu(a, j):
  return [-2*j, j * j + a]

def tami(x, ab):
  a, b = ab
  return a * x + b

def renritu(ab1, ab2):
  a1, b1 = ab1
  a2, b2 = ab2
  return (b2 - b1) / (a1 - a2)

def add(a, b):
  ab3 = nasu(a, b)
  while len(L) >= 2:
    ab1 = L[-2]
    ab2 = L[-1]
    x1 = renritu(ab1, ab2)
    x2 = renritu(ab2, ab3)
    if x1 > x2:
      L.pop()
    else:
      break
  L.append(ab3)

N, C = list(map(int, input().split()))
h = list(map(int, input().split()))

DP = [0] * N
L = [nasu(0, h[0])]

cnt = 0
for i in range(1, N):
  while cnt < len(L) - 1:
    x = tami(h[i], L[cnt])
    y = tami(h[i], L[cnt + 1])
    if x >= y:
      cnt += 1
    else:
      break
  DP[i] = h[i] ** 2 + C + tami(h[i], L[cnt])
  add(DP[i], h[i])

print(DP[-1])

Solution (Python):






import sys
input = sys.stdin.readline

import math

import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache





MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"






def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]



def DD(arg): return defaultdict(arg)


def inv(n): return pow(n, MOD-2, MOD)


kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret


def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr


def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors


def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum


def gcd(a, b):
    while b: a, b = b, a % b
    return a


def lcm(a, b):
    return a * b // gcd (a, b)


def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count


def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]


def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count





N,C = IL()
H = IL()

from collections import deque
deq = deque()
def check(f1, f2, f3):
  return (f2[0] - f1[0]) * (f3[1] - f2[1]) >= (f2[1] - f1[1]) * (f3[0] - f2[0])
def f(f1, x):
  return f1[0]*x + f1[1]


def add_line(a, b):
  f1 = (a, b)
  while len(deq) >= 2 and check(deq[-2], deq[-1], f1):
    deq.pop()
  deq.append(f1)


def query(x):
  while len(deq) >= 2 and f(deq[0], x) >= f(deq[1], x):
    deq.popleft()
  return f(deq[0], x)

dp = [0]

for i in range(1,N):
  add_line(-2*H[i-1],dp[-1]+H[i-1]**2)
  dp.append(query(H[i]) + H[i]**2 + C)

print(dp[-1])

while False and kokohazettaiyomarenaikarananikaitemoiindesuwahhahha: naniwarotennen

Solution (Python):






import sys
input = sys.stdin.readline

import math

import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache





MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"






def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]



def DD(arg): return defaultdict(arg)


def inv(n): return pow(n, MOD-2, MOD)


kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret


def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr


def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors


def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum


def gcd(a, b):
    while b: a, b = b, a % b
    return a


def lcm(a, b):
    return a * b // gcd (a, b)


def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count


def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]


def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count





N,C = IL()
H = IL()

from collections import deque
deq = deque()
def check(f1, f2, f3):
  return (f2[0] - f1[0]) * (f3[1] - f2[1]) >= (f2[1] - f1[1]) * (f3[0] - f2[0])
def f(f1, x):
  return f1[0]*x + f1[1]


def add_line(a, b):
  f1 = (a, b)
  while len(deq) >= 2 and check(deq[-2], deq[-1], f1):
    deq.pop()
  deq.append(f1)


def query(x):
  while len(deq) >= 2 and f(deq[0], x) >= f(deq[1], x):
    deq.popleft()
  return f(deq[0], x)

dp = [0]

for i in range(1,N):
  add_line(-2*H[i-1],dp[-1]+H[i-1]**2)
  dp.append(query(H[i]) + H[i]**2 + C)

print(dp[-1])

Solution (Python):
from collections import deque


def F(x, p, q):
    return x * p + q


def check(f1, f2, f3):
    a1, b1 = f1
    a2, b2 = f2
    a3, b3 = f3
    return (a2 - a1) * (b3 - b2) >= (b2 - b1) * (a3 - a2)


def main():
    N, C = map(int, input().split())
    H = list(map(int, input().split()))

    dp = 0
    line = deque()
    line.append((-2 * H[0], H[0] ** 2))
    i = 0

    for h in H[1:]:
        while i + 1 < len(line) and F(h, *line[i]) >= F(h, *line[i + 1]):
            i += 1
        dp = h ** 2 + C + F(h, *line[i])

        p = -2 * h
        q = h ** 2 + dp
        while len(line) >= 2 and check(line[-2], line[-1], (p, q)):
            line.pop()
        line.append((p, q))

    print(dp)


if __name__ == "__main__":
    main()

Solution (Python):
from collections import deque

def solve():
    class ConvexHullTrick:
        def __init__(self):
            self.LNows = deque()
            self.numL = 0

        def _isNotL2Min(self, L1, L2, L3):
            a1, b1 = L1
            a2, b2 = L2
            a3, b3 = L3
            return (a1-a2) * (b2-b3) >= (a2-a3) * (b1-b2)

        def _getY(self, L, x):
            a, b = L
            return a*x + b

        def addLine(self, L):
            while self.numL >= 2 and self._isNotL2Min(self.LNows[-2], self.LNows[-1], L):
                self.LNows.pop()
                self.numL -= 1
            self.LNows.append(L)
            self.numL += 1

        def getMin(self, x):
            y = self._getY(self.LNows[0], x)
            while self.numL >= 2:
                yNext = self._getY(self.LNows[1], x)
                if yNext > y: break
                y = yNext
                self.LNows.popleft()
                self.numL -= 1
            return y


    N, C = map(int, input().split())
    hs = list(map(int, input().split()))

    CHT = ConvexHullTrick()
    dp = [0] * N
    for i in range(1, N):
        CHT.addLine((-2*hs[i-1], dp[i-1] + hs[i-1]**2))
        minY = CHT.getMin(hs[i])
        dp[i] = minY + hs[i]**2 + C

    print(dp[-1])


solve()

Solution (Python):
from collections import deque
deq = deque()
def check(f1, f2, f3):
    return (f2[0] - f1[0]) * (f3[1] - f2[1]) >= (f2[1] - f1[1]) * (f3[0] - f2[0])
def f(f1, x):
    return f1[0]*x + f1[1]


def add_line(a, b):
    f1 = (a, b)
    while len(deq) >= 2 and check(deq[-2], deq[-1], f1):
        deq.pop()
    deq.append(f1)


def query(x):
    while len(deq) >= 2 and f(deq[0], x) >= f(deq[1], x):
        deq.popleft()
    return f(deq[0], x)

N,C=map(int,input().split())
h=list(map(int,input().split()))
dp=[0]*N
dp[-1]=0
add_line(2*h[-1],h[-1]**2)
for i in range(N-2,-1,-1):
    dp[i]=h[i]**2+C+query(-h[i])
    add_line(2*h[i],h[i]**2+dp[i])

print(dp[0])

Solution (Python):
import sys
input = sys.stdin.readline
from collections import *

class CHT: 
    def __init__(self):
        self.q = deque([]) 
        
    def f(self, f1, x): 
        return f1[0]*x+f1[1]
    
    def check(self, f1, f2, f3): 
        return (f2[0]-f1[0])*(f3[1]-f2[1])>=(f2[1]-f1[1])*(f3[0]-f2[0])
    
    def add_line(self, a, b): 
        while len(self.q)>=2 and self.check(self.q[-2], self.q[-1], (a, b)):
            self.q.pop()
        
        self.q.append((a, b))
    
    def get(self, x): 
        while len(self.q)>=2 and self.f(self.q[0], x)>=self.f(self.q[1], x):
            self.q.popleft()
        
        return self.f(self.q[0], x)
    
N, C = map(int, input().split())
h = list(map(int, input().split()))
dp = [0]*N
cht = CHT()
cht.add_line(-2*h[0], h[0]**2)

for i in range(1, N):
    dp[i] = h[i]**2+C+cht.get(h[i])
    cht.add_line(-2*h[i], dp[i]+h[i]**2)

print(dp[N-1])

Solution (Python):
import sys
input = sys.stdin.readline

class CHT: 
    def __init__(self, N): 
        self.deq = [0]*N
        self.l = 0
        self.r = 0
        
    def f(self, j, x): 
        return -2*h[j]*h[x]+dp[j]+h[j]**2
        
    def check(self, j1, j2, j3): 
        a1, b1 = -2*h[j1], dp[j1]+h[j1]**2
        a2, b2 = -2*h[j2], dp[j2]+h[j2]**2
        a3, b3 = -2*h[j3], dp[j3]+h[j3]**2
        
        return (a2-a1)*(b3-b2)>=(b2-b1)*(a3-a2)
    
    def add(self, j): 
        while self.l+1<self.r and self.check(self.deq[self.r-2], self.deq[self.r-1], j):
            self.r -= 1
        
        self.deq[self.r] = j
        self.r += 1
    
    def get(self, x): 
        while self.l+1<self.r and self.f(self.deq[self.l], x)>=self.f(self.deq[self.l+1], x):
            self.l += 1
        
        return self.f(self.deq[self.l], x)

N, C = map(int, input().split())
h = list(map(int, input().split()))
dp = [0]*N
cht = CHT(N)
cht.add(0)

for i in range(1, N):
    dp[i] = h[i]**2+C+cht.get(i)
    cht.add(i)
    
print(dp[N-1])

Solution (Python):
import sys
input = sys.stdin.readline


class LiChaoTree:
    """Convex Hull TrickをSegmentTree上で行う
    add_line: 直線集合に line = (傾きa, 切片b) の直線を追加する
    get_min: 座標xにおいて直線集合が取りうる最小値を求める
    """
    def __init__(self, x_coords):
        self.INF = 10 ** 20
        self.n = len(x_coords)
        self.size = 2 ** (self.n - 1).bit_length()
        self.to_ind = {x: ind for ind, x in enumerate(x_coords)}
        self.x_coords = x_coords + [self.INF] * (self.size - self.n)
        self.data = [None] * (2 * self.size)

    def add_line(self, line):
        """直線の集合に line = (傾きa, 切片b) の直線を追加する"""
        left = 0
        right = self.size
        k = 1
        while True:
            if self.data[k] is None:
                self.data[k] = line
                return

            mid = (left + right) // 2
            lx = self.x_coords[left]
            mx = self.x_coords[mid]
            rx = self.x_coords[right - 1]

            need_l_update = self.f(line, lx) < self.f(self.data[k], lx)
            need_m_update = self.f(line, mx) < self.f(self.data[k], mx)
            need_r_update = self.f(line, rx) < self.f(self.data[k], rx)

            if need_l_update and need_r_update:
                self.data[k] = line
                return

            if not need_l_update and not need_r_update:
                return

            if need_m_update:
                self.data[k], line = line, self.data[k]

            if need_l_update != need_m_update:
                right = mid
                k = 2 * k
            else:
                left = mid
                k = 2 * k + 1

    def f(self, line, x):
        """f(x)を求める"""
        a, b = line
        return a * x + b

    def get_min(self, x):
        """座標xにおいて直線集合が取りうる最小値を求める"""
        k = self.to_ind[x] + self.size
        res = self.INF
        while k > 0:
            if self.data[k] is not None:
                res = min(res, self.f(self.data[k], x))
            k = k >> 1
        return res


n, c = map(int, input().split())
h = list(map(int, input().split()))
INF = 10**20
 
lct = LiChaoTree(h)
dp = [INF] * n
dp[0] = 0
lct.add_line((-2 * h[0], h[0] ** 2 + dp[0]))
 
for i in range(1, n):
    dp[i] = lct.get_min(h[i]) + c + h[i] ** 2
    lct.add_line((-2 * h[i], h[i] ** 2 + dp[i]))
print(dp[-1])

Solution (Python):
import sys
input = sys.stdin.readline
N, C = map(int, input().split())
a = list(map(int, input().split()))

from collections import deque
deq = deque()
def check(f1, f2, f3):
    return (f2[0] - f1[0]) * (f3[1] - f2[1]) >= (f2[1] - f1[1]) * (f3[0] - f2[0])
def f(f1, x):
    return f1[0]*x + f1[1]


def add_line(a, b):
    f1 = (a, b)
    while len(deq) >= 2 and check(deq[-2], deq[-1], f1):
        deq.pop()
    deq.append(f1)


def query(x):
    while len(deq) >= 2 and f(deq[0], x) >= f(deq[1], x):
        deq.popleft()
    return f(deq[0], x)

add_line(-2 * a[0], a[0] ** 2 + C)
dp = [0] * N
for i in range(1, N):
  x = query(a[i]) + a[i] ** 2
  add_line(-2 * a[i], x + C + a[i] ** 2)
  dp[i] = x
print(dp[-1])

Solution (Python):
import sys
input = lambda : sys.stdin.readline().strip()

from collections import deque
from operator import le, ge

class Convex_Hull_Trick():
    def __init__(self, op=ge):
        self.que = deque()
        self.op = op

    @staticmethod
    def f(f1, x):
        return f1[0]*x + f1[1]

    def check(self, f1, f2, f3):
        a = (f2[0] - f1[0]) * (f3[1] - f2[1])
        b = (f2[1] - f1[1]) * (f3[0] - f2[0])
        return self.op(a, b)

    def add_line(self, a, b):
        que = self.que
        fi = (a, b)
        while len(que) >= 2 and self.check(que[-2], que[-1], fi):
            que.pop()
        que.append(fi)

    def get(self, x):
        que = self.que
        f = self.f
        while len(que) >= 2 and self.op(f(que[0], x), f(que[1], x)):
            que.popleft()
        return f(que[0], x)

n,c = map(int, input().split())
h = list(map(int, input().split()))

CHT = Convex_Hull_Trick()
CHT.add_line(-2*h[0], h[0]**2)

DP = [0]*n

for i in range(1, n):
    min_cost = CHT.get(h[i])
    DP[i] = min_cost + h[i]*h[i] + c
    CHT.add_line(-2*h[i], h[i]**2+DP[i])

print(DP[-1])

Solution (Python):
import sys
input = lambda : sys.stdin.readline().strip()

from collections import deque

class Convex_Hull_Trick():
    def __init__(self):
        self.que = deque()

    @staticmethod
    def check(f1, f2, f3):
        return (f2[0] - f1[0]) * (f3[1] - f2[1]) >= (f2[1] - f1[1]) * (f3[0] - f2[0])

    @staticmethod
    def f(f1, x):
        return f1[0]*x + f1[1]

    def add_line(self, a, b):
        fi = (a, b)
        while len(self.que) >= 2 and self.check(self.que[-2], self.que[-1], fi):
            self.que.pop()
        self.que.append(fi)

    def query(self, x):
        while len(self.que) >= 2 and self.f(self.que[0], x) >= self.f(self.que[1], x):
            self.que.popleft()
        return self.f(self.que[0], x)

n,c = map(int, input().split())
h = list(map(int, input().split()))

CHT = Convex_Hull_Trick()
CHT.add_line(-2*h[0], h[0]**2)

DP = [0]*n

for i in range(1, n):
    min_cost = CHT.query(h[i])
    DP[i] = min_cost + h[i]*h[i] + c
    CHT.add_line(-2*h[i], h[i]**2+DP[i])

print(DP[-1])

Solution (Python):
lines = []
def fi(i, x):
    a, b = lines[i]
    return a*x+b

def find(x):
    def f(i):
        return fi(i+1,x) > fi(i,x)
    mn, mx = -1, len(lines)-1
    idx = (mn+mx)//2
    while mx-mn>1:
        if f(idx):
            mx, idx = idx, (mn + idx)//2
            continue
        mn, idx = idx, (mx + idx)//2
    return fi(idx+1, x)

def find2(x):
    
    I = find2.I
    u, v = lines[I]
    while I+1<len(lines):
        w, y = lines[I+1]
        if u*x+v < w*x+y:
            break
        u, v = w, y
        I += 1
    find2.I = I
    return u*x+v
find2.I = 0

def insert(a, b):
    pass

def insert2(a, b):
    
    if not lines:
        lines.append((a,b))
        return
    (e, f) = lines[-1]
    while len(lines)-1:
        (c, d), (e, f) = (e, f), lines[-2]
        if (c-e)*(b-d) < (d-f)*(a-c):
            break
        lines.pop()
    lines.append((a, b))

N, C = map(int, input().split())
hs = map(int, input().split())
r = 0
lines = []
for i, h in enumerate(hs):
    if i!= 0:
        r = find(h) + h**2+C
    insert2(-2*h, r+h**2)
print(r)

Solution (Python):
N, C = map(int, input().split())
hs = list(map(int, input().split()))
ls = [(-2*hs[0], hs[0]**2)] + [0]*N
I,J = 0,0
for h in hs[1:]:
    u, v = ls[I]
    while I<J:
        w, y = ls[I+1]
        if u*h+v < w*h+y:
            break
        u, v, I = w, y, I+1
    a, b = -2*h, u*h+v+2*h**2+C
    while J:
        (c, d), (e, f) = ls[J], ls[J-1]
        if (c-e)*(b-d) < (d-f)*(a-c):
            break
        J-=1
    J+=1
    ls[J] = (a, b)
print(u*h+v + h**2+C)

Solution (Python):
N, C = map(int, input().split())
hs = list(map(int, input().split()))
lines = [(-2*hs[0], hs[0]**2)]
I = 0
for h in hs[1:]:
    u, v = lines[I]
    while I+1<len(lines):
        uu, vv = lines[I+1]
        if u*h+v < uu*h+vv:
            break
        u, v = uu, vv
        I += 1
    r = u*h+v + h**2+C
    a, b = -2*h, r+h**2
    (e, f) = lines[-1]
    while len(lines)-1:
        (c, d), (e, f) = (e, f), lines[-2]
        if (c-e)*(b-d) < (d-f)*(a-c):
            break
        lines.pop()
    lines.append((a, b))
print(r)

Solution (Python):
N, C = map(int, input().split())
hs = list(map(int, input().split()))
lines = [(-2*hs[0], hs[0]**2)]
I = 0
for h in hs[1:]:
    u, v = lines[I]
    while I+1<len(lines):
        uu, vv = lines[I+1]
        if u*h+v < uu*h+vv:
            break
        u, v = uu, vv
        I += 1
    r = u*h+v + h**2+C
    a, b = -2*h, r+h**2
    (e, f) = lines[-1]
    while len(lines)-1:
        (c, d), (e, f) = (e, f), lines[-2]
        if (c-e)*(b-d) < (d-f)*(a-c):
            break
        lines.pop()
    lines.append((a, b))
print(r)

Solution (Python):
def fi(i, x):
    a, b = lines[i]
    return a*x+b

def find(x):
    def f(i):
        return fi(i+1,x) > fi(i,x)
    mn, mx = -1, len(lines)-1
    idx = (mn+mx)//2
    while mx-mn>1:
        if f(idx):
            mx, idx = idx, (mn + idx)//2
            continue
        mn, idx = idx, (mx + idx)//2
    return fi(idx+1, x)

def insert(a, b):
    (e, f) = lines[-1]
    while len(lines)-1:
        (c, d), (e, f) = (e, f), lines[-2]
        if (c-e)*(b-d) < (d-f)*(a-c):
            break
        lines.pop()
    lines.append((a, b))

N, C = map(int, input().split())
hs = list(map(int, input().split()))
lines = [(-2*hs[0], hs[0]**2)]
for h in hs[1:]:
    r = find(h) + h**2+C
    insert(-2*h, r+h**2)
print(r)

Solution (Python):
def fi(i, x):
    a, b = lines[i]
    return a*x+b

def find(x):
    if len(lines) == 1:
        return 0
    def f(i):
        
        return fi(i+1,x) > fi(i,x)
    mn, mx = 0, len(lines)-2
    idx = (mn+mx)//2
    if f(mn):
        return 0
    if not f(mx):
        return mx+1
    while mx-mn>1:
        if f(idx):
            mx, idx = idx, (mn + idx)//2
            continue
        mn, idx = idx, (mx + idx)//2
    return idx+1

def remove_lines():
    (x, y) = lines.pop()
    a, b  = x, y
    (e, f) = lines[-1]
    while len(lines)-1:
        (c, d), (e, f) = (e, f), lines[-2]
        if (c-e)*(b-d) < (d-f)*(a-c):
            break
        lines.pop()
    lines.append((x, y))

def insert(a, b):
    lines.append((a, b))
    if len(lines) >= 3:
        remove_lines()

N, C = map(int, input().split())
hs = map(int, input().split())
r = 0
lines = []
for i, h in enumerate(hs):
    if i!= 0:
        r = fi(find(h), h) + h**2+C
    insert(-2*h, r+h**2)
print(r)

Solution (Python):
class LiChaoTree():
    """Convex Hull TrickをSegmentTree上で行う
    add_line: 直線集合に line = (傾きa, 切片b) の直線を追加する
    get_min: 座標xにおいて直線集合が取りうる最小値を求める
    """
    def __init__(self, x_coord_list):
        self.INF = 10**20
        self.n = len(x_coord_list)
        self.size = 2**(self.n-1).bit_length()
        self.to_ind = {x: ind for ind, x in enumerate(x_coord_list)}
        self.x_coord_list = x_coord_list + [self.INF] * (self.size - self.n)
        self.data = [None] * (2*self.size)

    def add_line(self, line):
        """直線の集合に line = (傾きa, 切片b) の直線を追加する"""
        left = 0
        right = self.size
        k = 1
        while True:
            if self.data[k] is None:
                self.data[k] = line
                return

            mid = (left + right) // 2
            lx = self.x_coord_list[left]
            mx = self.x_coord_list[mid]
            rx = self.x_coord_list[right - 1]

            need_l_update = (self.f(line, lx) < self.f(self.data[k], lx))
            need_m_update = (self.f(line, mx) < self.f(self.data[k], mx))
            need_r_update = (self.f(line, rx) < self.f(self.data[k], rx))

            if need_l_update and need_r_update:
                self.data[k] = line
                return

            if not need_l_update and not need_r_update:
                return

            if need_m_update:
                self.data[k], line = line, self.data[k]
            if need_l_update != need_m_update:
                right = mid
                k = 2*k
            else:
                left = mid
                k = 2*k + 1

    def f(self, line, x):
        """f(x)を求める"""
        a, b = line
        return a*x + b

    def get_min(self, x):
        """座標xにおいて直線集合が取りうる最小値を求める"""
        k = self.to_ind[x] + self.size 
        res = self.INF
        while k > 0:
            if self.data[k] is not None:
                res = min(res, self.f(self.data[k], x))
            k = k >> 1
        return res


n, c = map(int, input().split())
h = list(map(int, input().split()))
INF = 10**20

lct = LiChaoTree(h)
dp = [INF] * n
dp[0] = 0
lct.add_line((-2*h[0], h[0]**2 + dp[0]))

for i in range(1, n):
    dp[i] = lct.get_min(h[i]) + c + h[i]**2
    lct.add_line((-2*h[i], h[i]**2 + dp[i]))
print(dp[-1])

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from collections import deque

N,C,*H = map(int,read().split())

class ConvexHullTrick:
    """
    f_i = a_ix + b_i とする。f_i の追加および、min_i f(x) の取得ができるデータ構造。
    ただし、傾き a_i は昇順に追加されなければならない。
    また、クエリ x も昇順に実行されなければならない。
    """
    def __init__(self):
        self.funcs = deque()

    def add(self,a,b):
        funcs = self.funcs
        while len(funcs) >= 2:
            a1,b1 = funcs[-2]
            a2,b2 = funcs[-1]
            if (a2-a1)*(b-b2) < (b2-b1)*(a-a2):
                break
            funcs.pop()
        funcs.append((a,b))

    def query(self,x):
        funcs = self.funcs
        a,b = funcs[0]
        y = a*x+b
        while len(funcs) >= 2:
            a2,b2 = funcs[1]
            y2 = a2*x+b2
            if y < y2:
                break
            y = y2
            funcs.popleft()
        return y

dp = [0] * N
cht = ConvexHullTrick()
add = cht.add; query = cht.query

h = H[0]
add(-2*h, h*h)
for i,h in enumerate(H[1:],1):
    x = query(h) + h*h + C
    dp[i] = x
    add(-2*h, h*h + x)

answer = dp[-1]
print(answer)

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from collections import deque

N,C,*H = map(int,read().split())

class CHT:
    """
    f_i = a_ix + b_i とする。f_i の追加および、min_i f(x) の取得ができるデータ構造。
    ただし、傾き a_i は昇順に追加されなければならない。
    また、クエリ x も昇順に実行されなければならない。
    """
    def __init__(self):
        self.funcs = deque()

    def add(self,a,b):
        funcs = self.funcs
        while len(funcs) >= 2:
            a1,b1 = funcs[-2]
            a2,b2 = funcs[-1]
            if (a2-a1)*(b-b2) < (b2-b1)*(a-a2):
                break
            funcs.pop()
        funcs.append((a,b))

    def query(self,x):
        funcs = self.funcs
        a,b = funcs[0]
        y = a*x+b
        while len(funcs) >= 2:
            a2,b2 = funcs[1]
            y2 = a2*x+b2
            if y < y2:
                break
            y = y2
            funcs.popleft()
        return y

dp = [0] * N
cht = CHT()
add = cht.add; query = cht.query

h = H[0]
add(-2*h, h*h)
for i,h in enumerate(H[1:],1):
    x = query(h) + h*h + C
    dp[i] = x
    add(-2*h, h*h + x)

answer = dp[-1]
print(answer)

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from collections import deque

N,C,*H = map(int,read().split())

class CHT:
    """
    f_i = a_ix + b_i とする。f_i の追加および、min_i f(x) の取得ができるデータ構造。
    ただし、傾き a_i は昇順に追加されなければならない。
    また、クエリ x も昇順に実行されなければならない。
    """
    def __init__(self):
        self.funcs = deque()

    def add(self,a,b):
        funcs = self.funcs
        while len(funcs) >= 2:
            a1,b1 = funcs[-2]
            a2,b2 = funcs[-1]
            if (a2-a1)*(b-b2) < (b2-b1)*(a-a2):
                break
            funcs.pop()
        funcs.append((a,b))

    def query(self,x):
        funcs = self.funcs
        a,b = funcs[0]
        y = a*x+b
        while len(funcs) >= 2:
            a2,b2 = self.funcs[1]
            y2 = a2*x+b2
            if y < y2:
                break
            y = y2
            self.funcs.popleft()
        return y

dp = [0] * N
cht = CHT()

h = H[0]
add = cht.add
query = cht.query

add(-2*h, h*h)
for i,h in enumerate(H[1:],1):
    x = query(h) + h*h + C
    dp[i] = x
    add(-2*h, h*h + x)

answer = dp[-1]
print(answer)

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from collections import deque

N,C,*H = map(int,read().split())

class CHT:
    """
    f_i = a_ix + b_i とする。f_i の追加および、min_i f(x) の取得ができるデータ構造。
    ただし、傾き a_i は昇順に追加されなければならない。
    また、クエリ x も昇順に実行されなければならない。
    """
    def __init__(self):
        self.funcs = deque()

    def add(self,a,b):
        funcs = self.funcs
        while len(funcs) >= 2:
            a1,b1 = funcs[-2]
            a2,b2 = funcs[-1]
            if (a2-a1)*(b-b2) < (b2-b1)*(a-a2):
                break
            funcs.pop()
        funcs.append((a,b))

    def query(self,x):
        funcs = self.funcs
        a,b = funcs[0]
        y = a*x+b
        while len(funcs) >= 2:
            a2,b2 = self.funcs[1]
            y2 = a2*x+b2
            if y < y2:
                break
            y = y2
            self.funcs.popleft()
        return y

dp = [0] * N
cht = CHT()

h = H[0]
cht.add(-2*h, h*h)
for i,h in enumerate(H[1:],1):
    x = cht.query(h) + h*h + C
    dp[i] = x
    cht.add(-2*h, h*h + x)

answer = dp[-1]
print(answer)

Solution (Python):
import sys
read = sys.stdin.buffer.read

from collections import deque

N,C,*H = map(int,read().split())

dp = [0] * N
funcs = deque() 

def add(i):
    h = H[i]
    a3,b3 = -2*h,h*h+dp[i]
    while len(funcs) >= 2:
        a1,b1 = funcs[-2]
        a2,b2 = funcs[-1]
        if (a2-a1)*(b3-b2) < (b2-b1)*(a3-a2):
            break
        funcs.pop()
    funcs.append((a3,b3))

def get_min(x):
    a,b = funcs[0]
    y = a*x+b
    while len(funcs) >= 2:
        a2,b2 = funcs[1]
        y2 = a2*x+b2
        if y < y2:
            break
        y = y2
        funcs.popleft()
    return y

add(0)
for i,h in enumerate(H[1:],1):
    dp[i] = get_min(h) + h*h + C
    add(i)

answer = dp[-1]
print(answer)

Solution (Python):

import sys
input=sys.stdin.readline
from collections import deque

def check(l0,l1,l2):
    return (l2[1]-l1[1])*(l1[0]-l0[0])>=(l1[1]-l0[1])*(l2[0]-l1[0])

def f(l,x):
    return l[0]*x+l[1]

def add_line(a,b):
    while len(deq)>=2 and check(deq[-2],deq[-1],(a,b)):
        deq.pop()
    deq.append((a,b))

def query(x):
    while len(deq)>=2 and f(deq[0],x)>=f(deq[1],x):
        deq.popleft()
    return f(deq[0],x)


n,c=map(int,input().split())
h=[int(i) for i in input().split()]
d=[0]*n
deq=deque()
add_line(-2*h[0],h[0]**2+d[0])
for i in range(1,n):
    d[i]=query(h[i])+h[i]**2+c
    add_line(-2*h[i],h[i]**2+d[i])
print(d[-1])