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):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

from collections import deque

N,C = map(int,input().split())
H = [int(x) for x in input().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)

dp

answer = dp[-1]
print(answer)

Solution (Python):

class ConvexHullTrick:
	def __init__(self):
		self.AB = []

	def check(self,a,b):
		a1,b1 = self.AB[-1][0],self.AB[-1][1]
		a2,b2 = self.AB[-2][0],self.AB[-2][1]
		lhs = (b2-b1)*(a -a1)
		rhs = (b1-b )*(a1-a2)
		return lhs>=rhs

	
	
	def append(self,a,b):
		while 2<=len(self.AB) and self.check(a,b):
			self.AB.pop()
		self.AB.append((a,b))
		return
	
	def query(self,x):
		def eval(ab,x):
			return ab[0]*x+ab[1]
		l,r = -1, len(self.AB)-1
		while l+1<r:
			m = (l+r)//2
			if eval(self.AB[m+1],x)<=eval(self.AB[m],x):
				l = m
			else:
				r = m
		return eval(self.AB[r],x)

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


cht = ConvexHullTrick()

dp = [0]*N
dp[0] = 0
cht.append(-2*h[0],h[0]**2+dp[0])
for i in range(1,N):
	
	
	
	
	
	best = cht.query(h[i])
	dp[i] = best+h[i]**2+C

	cht.append(-2*h[i],h[i]**2+dp[i])

ans = dp[N-1]
print(ans)

Solution (Python):

class ConvexHullTrick:
	def __init__(self):
		self.AB = []

	def check(self,a,b):
		a1,b1 = self.AB[-1][0],self.AB[-1][1]
		a2,b2 = self.AB[-2][0],self.AB[-2][1]
		lhs = (b2-b1)*(a -a1)
		rhs = (b1-b )*(a1-a2)
		return lhs>=rhs

	
	
	def append(self,a,b):
		while 2<=len(self.AB) and self.check(a,b):
			self.AB.pop()
		self.AB.append((a,b))
		return
	
	def query(self,x):
		l,r = -1, len(self.AB)-1
		while l+1<r:
			m = (l+r)//2
			if self.eval(m+1,x)<=self.eval(m,x):
				l = m
			else:
				r = m
		return self.eval(r,x)
	def eval(self,k,x):
		a,b = self.AB[k][0],self.AB[k][1]
		return a*x+b

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


cht = ConvexHullTrick()

dp = [0]*N
dp[0] = 0
cht.append(-2*h[0],h[0]**2+dp[0])
for i in range(1,N):
	
	
	
	
	
	best = cht.query(h[i])
	dp[i] = best+h[i]**2+C

	cht.append(-2*h[i],h[i]**2+dp[i])

ans = dp[N-1]
print(ans)

Solution (Python):

class ConvexHullTrick:
	length = 0

	def __init__(self,size):
		self.A = [0]*size
		self.B = [0]*size

	def check(self,a,b):
		lhs = (self.B[self.length-2]-self.B[self.length-1])*(a-self.A[self.length-1])
		rhs = (self.B[self.length-1]-b)*(self.A[self.length-1]-self.A[self.length-2])
		return lhs>=rhs

	
	
	def add(self,a,b):
		while 2<=self.length and self.check(a,b):
			self.length -= 1
		self.A[self.length] = a
		self.B[self.length] = b
		self.length += 1
		return
	
	def query(self,x):
		l,r = -1, self.length-1
		while l+1<r:
			m = (l+r)//2
			if self.eval(m+1,x)<=self.eval(m,x):
				l = m
			else:
				r = m
		return self.eval(r,x)

	def eval(self,k,x):
		return self.A[k]*x + self.B[k]

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


cht = ConvexHullTrick(N)

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

	cht.add(-2*h[i],h[i]**2+dp[i])

ans = dp[N-1]
print(ans)

Solution (Python):
class Lichaotree:
    
    
    def __init__(self, X):
        self.N = len(X)
        self.N0 = 2**(self.N-1).bit_length()
        self.comp = {v : k for k, v in enumerate(X)}
        self.inf = 10**12
        self.X = X + [self.inf]*(self.N0 - self.N)
        self.data = [None]*(2*self.N0)
        self.size = [0]*self.N0 + [1]*self.N0
        for i in range(self.N0-1, 0, -1):
            self.size[i] = 2*self.size[2*i]
        self.start = [0]*(2*self.N0)
        for i in range(1, 2*self.N0):
            if i == i&(-i):
                continue
            self.start[i] = self.start[i-1] + self.size[i]
        
    def f(self, line, x):
        return line[0]*x + line[1]

    def _update(self, k, line):
        
        if self.data[k] is None:
            self.data[k] = line
            return
        
        l = self.start[k]
        r = l + self.size[k]        
        
        while True:
            if self.data[k] is None:
                self.data[k] = line
                return
            
            m = (l+r)//2
            lx = self.X[l]
            mx = self.X[m]
            rx = self.X[r-1]
            gl = (self.f(self.data[k], lx) > self.f(line, lx))
            gm = (self.f(self.data[k], mx) > self.f(line, mx))
            gr = (self.f(self.data[k], rx) > self.f(line, rx))
            if gl and gr:
                self.data[k] = line
                return
            
            if not gl and not gr:
                return
            
            if gm:
                self.data[k], line = line, self.data[k]
                gl = not gl
                
            if gl:
                r = m
                k = 2*k
            else:
                l = m
                k = 2*k+1
    
    def query(self, x):
        k = self.comp[x] + self.N0
        s = self.inf
        while k > 0:
            if self.data[k]:
                s = min(s, self.f(self.data[k], x))
            k = k >> 1
        return s
            
    def addline(self, line):
        self._update(1, line)
    
    def addlineseg(self, l, r, line):
        
        
        L = l+self.N0
        R = r+self.N0
        while L < R:
            if R & 1:
                R -= 1
                self._update(R, line)
            if L & 1:
                self._update(L, line)
                L += 1
            L >>= 1
            R >>= 1

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

T = Lichaotree(H)
dp = [10**19]*N
dp[0] = 0
T.addline((-2*H[0], H[0]**2))
for i in range(1,N):
    mi = T.query(H[i])
    dp[i] = mi + C + H[i]**2
    T.addline((-2*H[i], H[i]**2+dp[i]))
print(dp[-1])

Solution (Python):
class Lichaotree:
    
    
    def __init__(self, X):
        self.N = len(X)
        self.N0 = 2**(self.N-1).bit_length()
        self.comp = {v : k for k, v in enumerate(X)}
        self.inf = 10**19
        self.X = X + [self.inf]*(self.N0 - self.N)
        self.data = [None]*(2*self.N0)
        self.size = [0]*self.N0 + [1]*self.N0
        for i in range(self.N0-1, 0, -1):
            self.size[i] = 2*self.size[2*i]
        
    def f(self, line, x):
        return line[0]*x + line[1]

    def _update(self, k, line):
        
        if self.data[k] is None:
            self.data[k] = line
            return
        
        l = k - (1 << (k.bit_length() - 1))
        r = l + self.size[k]

        
        while True:
            if self.data[k] is None:
                self.data[k] = line
                return
            
            m = (l+r)//2
            lx = self.X[l]
            mx = self.X[m]
            rx = self.X[r-1]
            gl = (self.f(self.data[k], lx) > self.f(line, lx))
            gm = (self.f(self.data[k], mx) > self.f(line, mx))
            gr = (self.f(self.data[k], rx) > self.f(line, rx))
            if gl and gr:
                self.data[k] = line
                return
            
            if not gl and not gr:
                return
            
            if gm:
                self.data[k], line = line, self.data[k]
                gl = not gl
                
            if gl:
                r = m
                k = 2*k
            else:
                l = m
                k = 2*k+1
    
    def query(self, x):
        k = self.comp[x] + self.N0
        s = self.inf
        while k > 0:
            if self.data[k]:
                s = min(s, self.f(self.data[k], x))
            k = k >> 1
        return s
            
    def addline(self, line):
        self._update(1, line)

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

T = Lichaotree(H)
dp = [10**19]*N
dp[0] = 0
T.addline((-2*H[0], H[0]**2))
for i in range(1,N):
    mi = T.query(H[i])
    dp[i] = mi + C + H[i]**2
    T.addline((-2*H[i], H[i]**2+dp[i]))
print(dp[-1])

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=list(map(int,input().split()))
DP=[0]*n
deq=deque()
add_line(-2*H[0],H[0]**2+DP[0])
for i in range(1,n):
    DP[i]=query(H[i])+H[i]**2+c
    add_line(-2*H[i],H[i]**2+DP[i])
print(DP[-1])

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=list(map(int,input().split()))
DP=[0]*n
deq=deque()
add_line(-2*H[0],H[0]**2+DP[0])
for i in range(1,n):
    DP[i]=query(H[i])+H[i]**2+c
    add_line(-2*H[i],H[i]**2+DP[i])
print(DP[-1])

Solution (Python):




from collections import deque
deq = deque()


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


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


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


def get(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()))

INF = float('inf')
dp = [INF] * n
dp[0] = 0
add(-2 * h[0], h[0]**2 + dp[0])

for i in range(1, n):
    dp[i] = get(h[i]) + h[i]**2 + c
    add(-2 * h[i], h[i]**2 + dp[i])

print(dp[n-1])

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

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


DP=[0]*N















LINES=deque()
LINES.append([-2*H[0],DP[0]+H[0]**2])

for i in range(1,N):
    while len(LINES)>1 and LINES[0][0]*H[i]+LINES[0][1]>LINES[1][0]*H[i]+LINES[1][1]:
        LINES.popleft()
            
    DP[i]=LINES[0][0]*H[i]+LINES[0][1]+H[i]**2+C

    while True: 
        if len(LINES)<2:
            break
        
        a0,b0=LINES[-2]
        a1,b1=LINES[-1]
        a2,b2=-2*H[i],DP[i]+H[i]**2

        if (b0-b1)/(a0-a1)<=(b0-b2)/(a0-a2):
            LINES.pop()
        else:
            break
        
    LINES.append([-2*H[i],DP[i]+H[i]**2])

print(DP[-1])

Solution (Python):


from Queue import deque


n, c = map(int, raw_input().split())
h = map(int, raw_input().split())

dp = [0] * n
lines = deque([(-2 * h[n - 1], h[n - 1] ** 2)])
for i in range(n - 2, -1, -1):
    x = h[i]
    while len(lines) > 1:
        m1, n1 = lines[0]
        m2, n2 = lines[1]

        if m1 * x + n1 >= m2 * x + n2:
            lines.popleft()
        else:
            break

    mb, nb = lines[0]
    dp[i] = x * x + c + mb * x + nb

    mn = -2 * x
    nn = dp[i] + x * x
    while len(lines) > 1:
        m1, n1 = lines[-2]
        m2, n2 = lines[-1]
        if (nn - n2) * (m2 - m1) <= (n2 - n1) * (mn - m2):
            lines.pop()
        else:
            break
    lines.append((mn, nn))
print(dp[0])

Solution (Python):
n,C,*H=map(int,open(0).read().split());p=[0];P=[0]
for i in range(1,n):
 g=lambda x:(p[P[x-1]]-p[P[x]])/(H[P[x]]-H[P[x-1]])-H[P[x-1]]-H[P[x]]
 while len(P)>1and g(1)>-2*H[i]:P.pop(0)
 p+=[p[P[0]]+(H[P[0]]-H[i])**2+C];P+=[i]
 while len(P)>2and g(-1)>g(-2):P.pop(-2)
print(p[-1])

Solution (Python):
n,C,*H=map(int,open(0).read().split());p=[0];P=[0]
for i in range(1,n):
 g=lambda x,y:(p[P[y]]-p[P[x]])/(H[P[x]]-H[P[y]])-H[P[y]]-H[P[x]]
 while len(P)>1and g(1,0)>-2*H[i]:P.pop(0)
 p+=[p[P[0]]+(H[P[0]]-H[i])**2+C];P+=[i]
 while len(P)>2and g(-1,-2)>g(-2,-3):P.pop(-2)
print(p[-1])

Solution (Python):
n,C,*H=map(int,open(0).read().split());p=[0];P=[0]
for i in range(1,n):
 h=H[i];g=lambda x,y:(p[P[y]]-p[P[x]])/(H[P[x]]-H[P[y]])-H[P[y]]-H[P[x]]+2*h;
 while len(P)>1and g(1,0)>0:P.pop(0)
 p+=[p[P[0]]+(H[P[0]]-h)**2+C];P+=[i];h=0
 while len(P)>2and g(-1,-2)>g(-2,-3):P.pop(-2)
print(p[-1])

Solution (Python):
n,C,*H=map(int,open(0).read().split());p=[0];P=[0]
for i in range(1,n):
 h=H[i];g=lambda x,y:(p[P[y]]+H[P[y]]*(H[P[y]]-2*h)-p[P[x]]-H[P[x]]*(H[P[x]]-2*h))/(H[P[x]]-H[P[y]]);
 while len(P)>1and g(1,0)>0:P.pop(0)
 p+=[p[P[0]]+(H[P[0]]-h)**2+C];P+=[i];h=0
 while len(P)>2and g(-1,-2)>g(-2,-3):P.pop(-2)
print(p[-1])

Solution (Python):
n,C,*H=map(int,open(0).read().split());p=[0];P=[0]
for i in range(1,n):
 h=H[i];f=lambda I:p[P[I]]+H[P[I]]*(H[P[I]]-2*h)
 while len(P)>1and f(0)>f(1):P.pop(0)
 p+=[f(0)+h*h+C];h=0;P+=[i];g=lambda x,y:(f(y)-f(x))/(H[P[x]]-H[P[y]]);
 while len(P)>2and g(-1,-2)>g(-2,-3):P.pop(-2)
print(p[-1])

Solution (Python):
n,C,*H=map(int,open(0).read().split());p=[0];P=[0]
for i in range(1,n):
 h=H[i];f=lambda I:p[P[I]]+H[P[I]]*(H[P[I]]-2*h)
 while len(P)>1and f(0)>f(1):P.pop(0)
 p+=[f(0)+h*h+C];h=0;P+=[i]
 while len(P)>2and(H[P[-2]]-H[P[-3]])*(f(-2)-f(-1))>(H[i]-H[P[-2]])*(f(-3)-f(-2)):P.pop(-2)
print(p[-1])

Solution (Python):
n,C,*H=map(int,open(0).read().split());p=[0];P=[0]
for i in range(1,n):
 h=H[i];f=lambda I:p[I]+H[I]*(H[I]-2*h)
 while len(P)>1and f(P[0])>f(P[1]):P.pop(0)
 p+=[f(P[0])+h*h+C];h=0
 while len(P)>1and(H[P[-1]]-H[P[-2]])*(f(P[-1])-f(i))>(H[i]-H[P[-1]])*(f(P[-2])-f(P[-1])):P.pop()
 P+=[i]
print(p[-1])

Solution (Python):
n,C,*H=map(int,open(0).read().split());p=[0];P=[0]
for i in range(1,n):
 h=H[i];f=lambda I:p[I]+H[I]*(H[I]-2*h)
 while len(P)>1and f(P[0])>f(P[1]):P.pop(0)
 p+=[f(P[0])+h**2+C];h=0
 while len(P)>1and(H[P[-1]]-H[P[-2]])*(f(P[-1])-f(i))>(H[i]-H[P[-1]])*(f(P[-2])-f(P[-1])):P.pop()
 P+=[i]
print(p[-1])

Solution (Python):
n,C,*H=map(int,open(0).read().split());
dp=[0];
P=[0];
for i in range(1,n):
    h=H[i]
    f=lambda I:dp[I]+H[I]*(H[I]-2*h)
    while len(P)>1 and f(P[0])>f(P[1]):P.pop(0)
    dp+=[f(P[0])+h**2+C]
    h=0
    while len(P)>1 and (H[P[-1]]-H[P[-2]])*(f(P[-1])-f(i))>(H[i]-H[P[-1]])*(f(P[-2])-f(P[-1])):P.pop()
    P+=[i]
print(dp[-1])

Solution (Python):
n,C,*H=map(int,open(0).read().split());
dp=[0];
P=[0];
f=lambda I,h:dp[I]+H[I]*(H[I]-2*h)
for i in range(1,n):
    h=H[i]
    while len(P)>1 and f(P[0],h)>f(P[1],h):P.pop(0)
    dp+=[f(P[0],h)+h**2+C]
    while len(P)>1 and (H[P[-1]]-H[P[-2]])*(f(P[-1],0)-f(i,0))>(h-H[P[-1]])*(f(P[-2],0)-f(P[-1],0)):P.pop()
    P+=[i]
print(dp[-1])

Solution (Python):
n,C,*H=map(int,open(0).read().split());
dp=[0];
P=[0];
def f(I,h):
    return dp[I]+H[I]*(H[I]-2*h)
for i in range(1,n):
    h=H[i]
    while len(P)>1 and f(P[0],h)>f(P[1],h):P.pop(0)
    dp+=[f(P[0],h)+h**2+C]
    while len(P)>1 and (H[P[-1]]-H[P[-2]])*(f(P[-1],0)-f(i,0))>(h-H[P[-1]])*(f(P[-2],0)-f(P[-1],0)):P.pop()
    P+=[i]
print(dp[-1])

Solution (Python):
n,C,*H=map(int,open(0).read().split());
dp=[0];
P=[0];
def f(I,h):
    return dp[I]+H[I]*(H[I]-2*h)
def c(x,y,z):
    return (H[y]-H[x])*(f(y,0)-f(z,0))>(H[z]-H[y])*(f(x,0)-f(y,0))
for i in range(1,n):
    while len(P)>1 and f(P[0],H[i])>f(P[1],H[i]):P.pop(0)
    dp+=[f(P[0],H[i])+H[i]**2+C]
    while len(P)>1 and c(P[-2],P[-1],i):P.pop()
    P+=[i]
print(dp[-1])

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, = map(int, input().split())

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

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, = map(int, input().split())

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