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: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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):
    # 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):
    # a が単調減少
    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)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read

from collections import deque

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

dp = [0] * N
funcs = deque() # ax + b

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)

Submission status: Accepted

Solution code:
# from https://atcoder.jp/contests/dp/submissions/4751518
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])

Submission status: Accepted

Solution code:
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() # ax + b

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)

Submission status: Accepted

Solution code:

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

	# 一次関数 y=a*x+b を追加
	# 追加の際、傾きaは単調減少（既存の傾きより最小？）であること
	def append(self,a,b):
		while 2<=len(self.AB) and self.check(a,b):
			self.AB.pop()
		self.AB.append((a,b))
		return
	# min_i {a[i]*x+b[i]}
	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()))
#print(h)

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 = 99999999999999
	# for j in range(i):
	# 	#cost = dp[j]+(h[i]-h[j])**2+C
	# 	cost = (-2*h[j])*h[i]+(h[j]**2+dp[j])
	# 	best = min(best,cost)
	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)

Submission status: Accepted

Solution code:

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

	# 一次関数 y=a*x+b を追加
	# 追加の際、傾きaは単調減少（既存の傾きより最小？）であること
	def append(self,a,b):
		while 2<=len(self.AB) and self.check(a,b):
			self.AB.pop()
		self.AB.append((a,b))
		return
	# min_i {a[i]*x+b[i]}
	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()))
#print(h)

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 = 99999999999999
	# for j in range(i):
	# 	#cost = dp[j]+(h[i]-h[j])**2+C
	# 	cost = (-2*h[j])*h[i]+(h[j]**2+dp[j])
	# 	best = min(best,cost)
	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)

Submission status: Accepted

Solution code:

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

	# 直線の傾きaは単調現象であること
	# Add a line y=a*x+b
	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
	# min_i {a[i]*x+b[i]}
	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()))
#print(h)

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 = 99999999999999
	# for j in range(i):
	# 	#cost = dp[j]+(h[i]-h[j])**2+C
	# 	cost = (-2*h[j])*h[i]+(h[j]**2+dp[j])
	# 	best = min(best,cost)
	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)

Submission status: Accepted

Solution code:
class Lichaotree:
    #区間は1-indexed
    #min
    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, r)にlineを追加,l, rはXの元
        
        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])

Submission status: Accepted

Solution code:
class Lichaotree:
    #区間は1-indexed
    #min
    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])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# 追加クエリにおける直線の傾きが単調であり、最小値クエリにおけるxが単調である時の Convex-Hull Trick
# もっと言うと、今回は追加クエリの傾きが単調減少で、最小値クエリにおけるxが単調増加
# 参考 : http://satanic0258.hatenablog.com/entry/2016/08/16/181331

from collections import deque
deq = deque()

# 直線 l1, l2, l3のうち l2が不必要かどうか (不必要なら1, 必要なら0を返す)
def check(f1, f2, f3):
    return (f3[1] - f2[1]) * (f2[0] - f1[0]) >= (f2[1] - f1[1]) * (f3[0] - f2[0])

# f1(x)を返す
def f(f1, x):
    return f1[0] * x + f1[1]

# 直線 y = ax + b を追加
def add(a, b):
    # 直線 l1: deq[-2], l2: deq[-1], l3: (a, b)のうち, l2が不必要なら除くことを繰り返す
    while len(deq) >= 2 and check(deq[-2], deq[-1], (a, b)):
        deq.pop()
    deq.append((a, b))

#
def get(x):
    # 今回はクエリのxが単調増加であることを利用する
    # すると、あるクエリに置いて f1(x0) >= f2(x0)となればそれ以降(x > x0)でf1は最小となることはないので, f1を取り除く
    while len(deq) >= 2 and f(deq[0], x) >= f(deq[1], x):
        deq.popleft()
    # 上の操作後、deq の先頭が最小になるのでそれを返す
    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])

Submission status: Accepted

Solution code:
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#コストの最小値.DP[0]=0

#i番目では,
#j番目(0<=j<i)のうちで
#DP[j]+(H[j]-H[i])**2+Cが最小になるものを取る

#展開して
#DP[j]+C+H[j]**2+H[i]**2-2*H[i]*H[j]

#つまり
#x=H[i]として,
#-2*H[j]*x+(DP[j]+H[j]**2)
#が最小になるものを求めれば良い

#DP[i]=(この最小値)+H[i]**2+C

LINES=deque()#直線を表す[a,b]でax+b
LINES.append([-2*H[0],DP[0]+H[0]**2])#h_0に関する直線

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):#Hの単調性より分母は0にならない
            LINES.pop()
        else:
            break
        
    LINES.append([-2*H[i],DP[i]+H[i]**2])

print(DP[-1])

Submission status: Accepted

Solution code:


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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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