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

Submission status: Accepted

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

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

Submission status: Runtime Error

Solution code:
from heapq import heappop,heappush

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

ans = (h[-1]-h[0])**2

hq = []
hq_done = []
dif = [0]
dif += [i-j for i,j in zip(h[1:],h[:-1])]
left = list(range(-1,n))
right = list(range(1,n+2))

for i in range(1,n-1):
    di,dj = dif[i:i+2]
    cost = 2*di*dj
    heappush(hq,(cost,i))

now = c*(n-1)
for d in dif:
    now += d**2
ans = now

def hq_pop():
    while(hq_done):
        if(hq_done[0] == hq[0]):
            heappop(hq)
            heappop(hq_done)
        else:
            break

    return heappop(hq)

# print('')
# print(-1, now,ans)
# print(hq)
# print(hq_done)
# print(dif)
# print(left)
# print(right)

for _ in range(n-2):
    cost,l = hq_pop()
    now += cost - c
    ans = min(ans,now)

    r = right[l]
    ll = left[l]
    rr = right[r]
    d_new = dif[l] + dif[r]
    if(ll > 0):
        heappush(hq_done, (2*dif[ll]*dif[l],ll))
        heappush(hq,(2*dif[ll]*d_new,ll))
    if(rr < n):
        heappush(hq_done, (2*dif[r]*dif[rr],r))
        heappush(hq,(2*dif[rr]*d_new,ll))

    dif[l] = d_new
    dif[r] = 0
    right[l] = rr
    left[rr] = l

    # print('')
    # print(_, now,ans)
    # print(hq)
    # print(hq_done)
    # print(dif)
    # print(left)
    # print(right)

print(ans)

Submission status: Runtime Error

Solution code:
from heapq import heappop,heappush

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

ans = (h[-1]-h[0])**2

hq = []
hq_done = []
dif = [0]
dif += [i-j for i,j in zip(h[1:],h[:-1])]
left = list(range(-1,n))
right = list(range(1,n+2))

for i in range(1,n-1):
    di,dj = dif[i:i+2]
    cost = 2*di*dj
    heappush(hq,(cost,i))

now = c*(n-1)
for d in dif:
    now += d**2
ans = now

def hq_pop():
    while(hq_done):
        if(hq_done[0] == hq[0][0]):
            heappop(hq)
            heappop(hq_done)
        else:
            break

    return heappop(hq)

for _ in range(n-2):
    cost,l = hq_pop()
    now += cost - c
    ans = min(ans,now)

    r = right[l]
    ll = left[l]
    rr = right[r]
    d_new = dif[l] + dif[r]
    if(ll > 0):
        heappush(hq_done, 2*dif[ll]*dif[l])
        heappush(hq,(2*dif[ll]*d_new,ll))
    if(rr < n):
        heappush(hq_done, 2*dif[r]*dif[rr])
        heappush(hq,(2*dif[rr]*d_new,ll))

    dif[l] = d_new
    dif[r] = 0
    right[l] = rr
    left[rr] = l

print(ans)

Submission status: Runtime Error

Solution code:
N=int(input())
C=int(input())
lst=[]
for i in range(N):
  ele=int(input())
  lst.append(ele)
dp=[10**20]*(N+1)
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: Runtime Error

Solution code:
n, c = map(int, input().split())
h = list(map(int, input().split()))
import sys
import math
dp = [math.inf 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: Runtime Error

Solution code:
n, c = map(int, input().split())
h = list(map(int, input().split()))
import math
dp = [math.inf 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: Runtime Error

Solution code:
#include <bits/stdc++.h>
#define int long long
using namespace std;
    
int n, c;
int dp[2*100005];
int h[2*100005];

int parcours(int etape){
    if (etape < 0) return 1e15;
    if (dp[etape]) return dp[etape];
    if (etape == 0) return 0;

    int cur = 1e15;

    for (int i = 0; i < etape; i++)
        cur = min(cur, parcours(i) + (h[i] - h[etape])*(h[i] - h[etape]) + c);
    
    dp[etape] = cur; 
    return cur;
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> c;
    for (int i = 0; i < n; i++){
        cin >> h[i];
    }
    
    cout << parcours(n-1);

}

Submission status: Runtime Error

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 = fi(find(h), h) + h**2+C
    insert(-2*h, r+h**2)
print(r)

Submission status: Runtime Error

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:
                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: Runtime Error

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.data = [None] * (2*self.size)

    def add_line(self, line):
        """直線の集合に line = (傾きa, 切片b) の直線を追加する"""
        left = 0
        right = self.n
        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:
                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: Runtime Error

Solution code:
class LiChaoTree():
    """Convex Hull TrickをSegmentTree上で行う
    add_line: 直線集合に line = (傾きa, 切片b) の直線を追加する
    get_min: 座標xにおいて直線集合が取りうる最小値を求める
    """
    def __init__(self, x_coord_list):
        self.INF = 2**31 - 1
        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.data = [None] * (2*self.size)

    def add_line(self, line):
        """直線の集合に line = (傾きa, 切片b) の直線を追加する"""
        left = 0
        right = self.n
        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:
                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**18

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: Runtime Error

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

return l[0]

Submission status: Runtime Error

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(helper(h, n, c))

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
N, C = map(int, input().split(' '))
memo = [-1] * 200001
h = list(map(int, input().split(' ')))

def solve(atual, custo):
	if atual >= N-1:
		return custo
	
	if memo[atual] != -1:
		return memo[atual] + custo

	pula = float("inf")

	for i in range(atual+1, N):
		pula = min(pula, solve(i, custo + (h[i] - h[atual]) ** 2 + C))

	memo[atual] = pula - custo
	return pula

print(solve(0,0))