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.



Sample input:
5 6
1 2 3 4 5


Sample output:
20

Submission status: Time Limit Exceeded

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n,c = list(map(int, input().split()))
h = list(map(int, input().split()))
dp = [0]*n
from queue import deque
q = deque([(-2*h[0], h[0]**2)])
for i in range(1,n):
    while len(q)>=2 and q[-2][0]*h[i]+q[-2][1]<=q[-1][0]*h[i]+q[-1][1]:
        q.pop()
    dp[i] = min(item[0]*h[i]+item[1] for item in q) + h[i]**2 + c
#     dp[i] = q[-1][0]*h[i]+q[-1][1] + h[i]**2 + c
    q.appendleft((-2*h[i], h[i]**2 +dp[i]))
ans = dp[n-1]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
size, c = map(int, input().split())
arr = list(map(int, input().split()))
dp = [0]*(size)
dp[0] = 0
dp[1] = (arr[1] - arr[0])**2 + c
for i in range(2,size):
    dp[i] = min(dp[j] + (arr[j]-arr[i])**2 + c for j in range(i-1, -1, -1))

print(dp[size-1])

Submission status: Time Limit Exceeded

Solution code:
l=list(map(int,input().split()))
N=l[0]
C=l[1]
dp=[]
for i in range(N+2):
  dp.append(10**30)
dp[0]=0
lst=list(map(int,input().split()))
for i in range(N):
  for j in range(1,N):
    if(i+j<N):
      dp[i+j]=min(dp[i+j],dp[i]+(lst[i+j]-lst[i])**2+C)
print(dp[N-1])

Submission status: Time Limit Exceeded

Solution code:
N, C = map(int, input().split())
h = list(map(int, input().split()))
INF = float('inf')
dp = [INF for i in range(N)]
dp[0] = 0
for i in range(1,N):
    for j in range(i):
        dp[i] = min(dp[i], dp[i-j-1] + (h[i-j-1] - h[i])**2 + C)
print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:

def s0():return input()
def s1():return input().split()
def s2(n):return [input() for x in range(n)]
def s3(n):return [input().split() for _ in range(n)]
def s4(n):return [[x for x in s] for s in s2(n)]
def n0():return int(input())
def n1():return [int(x) for x in input().split()]
def n2(n):return [int(input()) for _ in range(n)]
def n3(n):return [[int(x) for x in input().split()] for _ in range(n)]
def t3(n):return [tuple(int(x) for x in input().split()) for _ in range(n)]
def p0(b,yes="Yes",no="No"): print(yes if b else no)
# from sys import setrecursionlimit
# setrecursionlimit(1000000)
# from collections import Counter,deque,defaultdict
# import itertools
# import math
# import networkx as nx
# from bisect import bisect_left,bisect_right
# from heapq import heapify,heappush,heappop
n,c=n1()
H=n1()

dp=[float("inf")]*n
dp[0]=0
for i in range(0,n):
    for j in range(1,n):
        if i+j<n:
            dp[i+j]=min(dp[i+j],dp[i]+(H[i]-H[i+j])**2+c)

print(dp[n-1])

Submission status: Time Limit Exceeded

Solution code:
n, c = map(int, input().split())
h = list(map(int, input().split()))
import sys
import math
dp = [10**17 for i in range(n)]
dp[0] = 0

for i in range(n):
    for j in range(n):
        if i + j < n:
            dp[i + j] = min(dp[i] + (h[i] - h[i + j])**2 + c, dp[i + j])
print(dp[n - 1])

Submission status: Time Limit Exceeded

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

    INF = float('INF')

    dp = [INF for _ in range(N)]
    dp[0] = 0

    for i in range(1, N):
        for j in range(0, i):
            cost = dp[j] + (H[i] - H[j]) ** 2 + C
            if cost < dp[i]:
                dp[i] = cost

    # print(dp)
    print(dp[N - 1])


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

n, c = map(int, input().split())
h = np.array(input().split(), dtype=np.int)
cost = np.zeros(n, dtype=np.int)
for i in range(1, n):
  diff = h[:i] - h[i]
  cost[i] = np.min(cost[:i] + diff * diff + c)
print(cost[-1])

Submission status: Time Limit Exceeded

Solution code:
n,c= map(int,input().split())
h1=list(map(int,input().split()))
if n==2:
    print(((h1[0]-h1[n-1])**2)+c)
    
else:
    dp=[-1]*n
    dp[n-1]=0
    for u in range(2,n+1):
     i=(n-u)
     dp[i]=min([dp[h]+(h1[h]-h1[i])**2+c for h in range(i+1,n)])
    print(dp[0])

Submission status: Time Limit Exceeded

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


dp = [0]*(n+5)


def parcours(etape):
    if etape < 0: return float("inf")
    if dp[etape]: return dp[etape]
    if etape == 0:
        return 0

    cur = float("inf")

    for i in range(etape):
        cur = min(cur, parcours(i) + (h[i] - h[etape])**2 + c)
    
    dp[etape] = cur 
    return cur

print(parcours(n-1))

Submission status: Time Limit Exceeded

Solution code:
n,c=map(int,input().split())
h=list(map(int,input().split()))
dp=[0]*n
for i in range(1,n):
    dp[i] = min(dp[j]+((h[i]-h[j])**2)+c for j in range(i))
print(dp[n-1])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
def fi(i, x):
    a, b = lines[i]
    return a*x+b

def find(x):
    if len(lines) == 1:
        return 0
    def f(i):
        # 0<=i<len(lines)-1
        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.popleft()
    a, b = x, y
    (e, f) = lines[0]
    while len(lines)-1:
        (c, d), (e, f) = (e, f), lines[1]
        if (c-e)*(b-d) < (d-f)*(a-c):
            break
        lines.popleft()
    lines.appendleft((x, y))

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

N, C = map(int, input().split())
hs = map(int, input().split())
r = 0
lines = deque([])
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)

Submission status: Time Limit Exceeded

Solution code:
import sys
n,c=list(int(i) for i in input().split())
A=list(int(i) for i in input().split())
dp=[0 for i in range(n)]
for i in range(1,n):
    x=10**13
    for j in range(1,n):
        if(i-j>=0):
            x=min(x,dp[i-j]+(A[i]-A[i-j])**2+c)
    dp[i]=x
print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
x1 = input()
x2 = input()

N = int(x1.split()[0])
C = int(x1.split()[1])
h = [int(z) for z in x2.split()]

l = [1e+10] * N
l[N-1] = 0
l[N-2] = (h[N-1] - h[N-2])**2 + C
for i in range(N-3, -1, -1):
  for j in range(i+1, N):
    l[i] = min(l[i], (h[j] - h[i])**2 + C + l[j])

print(l[0])

Submission status: Time Limit Exceeded

Solution code:
def helper3(h, n, c):
    res = [0]*n
    for i in range(1, n):
        hidden = []
        j = 1
        while i-j >= 0 and j < n:
            hidden.append(res[i-j]+(h[i]-h[i-j])**2+c)
            j += 1
        res[i] = min(hidden)
        #print(hidden)
    return res[-1]

def main():
    n, c = map(int, input().split())
    h = list(map(int, input().split(" ")))
    print(helper3(h, n, c))

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
INFTY = 10**13
N,C = map(int,input().split())
H = list(map(int,input().split()))
dp = [INFTY for _ in range(N)]
dp[N-1] = 0
for i in range(N-2,-1,-1):
    dp[i] = dp[i+1]+(H[i+1]-H[i])**2+C
    for j in range(i+2,N):
        if (H[j]-H[i])**2+C>=dp[i]:
            break
        dp[i] = min(dp[i],dp[j]+(H[j]-H[i])**2+C)
print(dp[0])

Submission status: Time Limit Exceeded

Solution code:
import sys
# inputを高速化する。
input = sys.stdin.readline

n,c=map(int,input().split())
h=list(map(int,input().split()))
INF=10**20
cost=[INF]*(n+1)
cost[0]=0

for i in range(0,n):
    for j in range(1,min(n+1,n-i)):
        cost[i+j]=min(cost[i+j],cost[i]+(h[i+j]-h[i])**2+c)

print(cost[n-1])

Submission status: Time Limit Exceeded

Solution code:
#flog3

n, c = map(int, input().split())
height = list(map(int,input().split()))
cost = [0]
cost.append(c + (height[0]-height[1])**2)

for i in range(2,n):
    dp_ = [cost[j] + c + (height[i]-height[j])**2 for j in range(i)]
    cost.append(min(dp_))
    
print(cost[-1])

Submission status: Time Limit Exceeded

Solution code:
n, c = map(int, input().split())

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

dp = [(h[i]-h[0])**2 + c for i in range(n)]

dp[0] = 0

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

Submission status: Time Limit Exceeded

Solution code:

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

dp = [0]*N
dp[0] = 0
for n in range(1,N):
	best = 99999999999999
	for k in range(1,N):
		if n-k<0: continue
		step = C+(h[n]-h[n-k])**2+dp[n-k]
		best = min(best,step)
	dp[n] = best

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

Submission status: Time Limit Exceeded

Solution code:
n,c = map(int,input().split())
l = list(map(int,input().split()))
l_ans = [0]*n
for i in range(1,n):
    tmp1=float("inf")
    for j in range(i):
        tmp2=l_ans[j]+(l[i]-l[j])**2+c
        if tmp1>tmp2:tmp1=tmp2
    l_ans[i]=tmp1
print(l_ans[::-1][0])

Submission status: Time Limit Exceeded

Solution code:
def f(n, c):
    hs = list(map(int, input().split()))
    dp = [0] * n
    for i in range(1, n):
        dp[i] = min(dp[j] + (hs[i] - hs[j]) ** 2 + c for j in range(i))
    print(dp[-1])


n, c = map(int, input().split())
f(n, c)

Submission status: Time Limit Exceeded

Solution code:
def f(n, c):
    hs = list(map(int, input().split()))
    dp = [0] * n
    for i, h in enumerate(hs):
        if i == 0: continue
        dp[i] = min(dp[j] + (h - hs[j]) ** 2 + c for j in range(i))
    print(dp[-1])


n, c = map(int, input().split())
f(n, c)

Submission status: Time Limit Exceeded

Solution code:
n, c = map(int, input().split())
hs = list(map(int, input().split()))
dp = [0] * n
for i, h in enumerate(hs):
    if i == 0: continue
    dp[i] = min(dp[j] + (h - hs[j]) ** 2 + c for j in range(i))
print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
input = stdin.readline

N, C = map(int, input().split())
h = list(map(int, input().split()))
c = [0] + [float('inf')] * N
for i in range(1, N):
    for j in range(i):
        c[i] = min(c[i], c[j] + (h[i] - h[j])**2 + C)
print(c[N - 1])

Submission status: Time Limit Exceeded

Solution code:
n,c=map(int,input().split())
h=[int(i) for i in input().split()]
#print(n,c,h)
dp=[0]*n
for i in range(1,n):
    a=[]
    for j in range(i):
        a.append(dp[j]+(h[j]-h[i])**2+c)
    dp[i]=min(a)
    #print('i,dp=',i,dp)
print(dp[n-1])

Submission status: Time Limit Exceeded

Solution code:
N, C = map(int, input().split())
h=[int(x) for x in input().split()]

dp=[0]*N
for i in range(1,N):
    j=i-1
    dp[i]=dp[j] + (h[i]-h[j])**2 + C
    while j>0: 
        j=j-1  
        if dp[i]>(dp[j] + (h[i]-h[j])**2 + C):
            dp[i]=dp[j] + (h[i]-h[j])**2 + C

print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
N, C = map(int, input().split())
h=[int(x) for x in input().split()]

dp=[0]*N
for i in range(1,N):
    dp[i]=min( [ ((h[i]-h[j])**2 + C + dp[j]) for j in range(i)] )

print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
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])

Submission status: Time Limit Exceeded

Solution code:
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])

Submission status: Time Limit Exceeded

Solution code:
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)
c=lambda x,y,z:(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):
    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 c(P[-2],P[-1],i):P.pop()
    P+=[i]
print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
N, C = map(int, input().split())
H = [int(h) for h in input().split()]

cost = [0]

for n in range(1,N):
    cost.append(min(map(lambda x: x[0]+(H[n]-x[1])**2+C, zip(cost, H))))

print(cost[-1])

Submission status: Time Limit Exceeded

Solution code:
N, C = map(int, input().split())
H = [int(h) for h in input().split()]

cost = [0]

for n in range(1,N):
    cost.append(min([cost[i] + (H[n]-H[i])**2 + C for i in range(n)]))

print(cost[-1])

Submission status: Time Limit Exceeded

Solution code:
n, c = input().split(" ")
n = int(n); c = int(c)
h = input().split(" ")
h = list(map(int, h))
result = [0]
for i in range(1, n):
    min = result[i - 1] + (h[i] - h[i - 1]) * (h[i] - h[i - 1]) + c
    if i >= 2:
        for j in range(2, i + 1):
            jump_j = result[i - j] + (h[i] - h[i - j]) * (h[i] - h[i - j]) + c
            if min > jump_j:
                min = jump_j
    result.append(min)
print(result[n - 1])

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

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

#############
# Functions #
#############

######INPUT######
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)]


#####Shorten#####
def DD(arg): return defaultdict(arg)

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

######Combination######
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

######Factorization######
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

#####MakeDivisors######
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

#####MakePrimes######
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

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

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

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

#####ChangeBase#####
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]

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

#############
# Main Code #
#############

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]

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

# min f_i(x)
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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

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

#############
# Functions #
#############

######INPUT######
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)]


#####Shorten#####
def DD(arg): return defaultdict(arg)

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

######Combination######
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

######Factorization######
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

#####MakeDivisors######
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

#####MakePrimes######
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

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

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

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

#####ChangeBase#####
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]

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

#############
# Main Code #
#############

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]

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

# min f_i(x)
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])

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
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]

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

# min f_i(x)
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])

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from collections import *

class CHT: #傾きの単調性と最小値クエリのxの単調性を仮定
    def __init__(self):
        self.q = deque([]) #直線群
        
    def f(self, f1, x): #f1(x)
        return f1[0]*x+f1[1]
    
    def check(self, f1, f2, f3): #f2を削除しても良いかの判定
        return (f2[0]-f1[0])*(f3[1]-f2[1])>=(f2[1]-f1[1])*(f3[0]-f2[0])
    
    def add_line(self, a, b): #傾き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): #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])

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

class CHT: #追加される直線の傾きと最小値クエリのxが単調と仮定
    def __init__(self, N): #N:直線数
        self.deq = [0]*N
        self.l = 0
        self.r = 0
        
    def f(self, j, x): #fj(x)
        return -2*h[j]*h[x]+dp[j]+h[j]**2
        
    def check(self, j1, j2, j3): #fj2を削除して良いか判定
        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): #直線群にfjを追加
        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): #fj(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])

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
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]

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

# min f_i(x)
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])