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: Wrong Answer

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()
A = IL()

dp = [0]

def cost(i,x):
  return dp[N-i-2-x] + (A[i+1+x]-A[i])**2 + C

def is_ok(i,mid1,mid2):
  if cost(i,mid1)>cost(i,mid2):
    return True
  else:
    return False

def meguru_bisect(i,ng, ok):
  if ok - ng == 2:
    return cost(i,ng+1)
  while (abs(ok - ng) > 2):
    mid1 = (ok*2 + ng) // 3
    mid2 = (ok + ng*2) // 3
    if is_ok(i,mid1,mid2):
      ok = mid1
    else:
      ng = mid2
  return min(cost(i,mid1),cost(i,mid2))

for i in range(N-1)[::-1]:
  dp.append(min((A[-1]-A[i])**2 + C,meguru_bisect(i,-1,N-1-i)))

print(dp[-1])

Submission status: Wrong Answer

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()
A = IL()

dp = [0]

def cost(i,x):
  return dp[N-i-2-x] + (A[i+1+x]-A[i])**2 + C

def is_ok(i,mid1,mid2):
  if cost(i,mid1)>cost(i,mid2):
    return True
  else:
    return False

def meguru_bisect(i,ng, ok):
  if ok - ng == 2:
    return cost(i,ng+1)
  while (abs(ok - ng) > 2):
    mid1 = (ok*2 + ng) // 3
    mid2 = (ok + ng*2) // 3
    if is_ok(i,mid1,mid2):
      ok = mid1
    else:
      ng = mid2
  return min(cost(i,mid1),cost(i,mid2))

for i in range(N-1)[::-1]:
  dp.append(meguru_bisect(i,-1,N-1-i))

print(dp[-1])

Submission status: Wrong Answer

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,l))

    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: Wrong Answer

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] = 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: Wrong Answer

Solution code:
#!/usr/bin python3
# -*- coding: utf-8 -*-

import numpy as np

def main():
    N, C = map(int, input().split())
    h = list(map(int, input().split()))
    INF = 10**10
    #dp[i]　iの位置に到達する最小の値
    dp = [INF]*N
    dp[0] = 0
    dp = np.array(dp)
    h = np.array(h)
    for i in range(N):
        dp[i+1:] = np.minimum(dp[i+1:], dp[i] + abs(h[i+1:]-h[i])**2+C)
    print(dp[N-1])

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
def solve(n, c, h):
    dp = [float('inf')]*n
    dp[0] = 0
    def _val(newpos, pos):
        return dp[pos] + c + (h[newpos] - h[pos])**2
    for i in range(1, n):
        l, r = 0, i-1
        while l < r:
            mid = l + (r-l)//2
            if _val(i, mid) >= _val(i, mid+1):
                l = mid + 1
            else:
                r = mid
        dp[i] = _val(i, l)
        # for j in range(i):
        #     dp[i] = min(dp[i], dp[j] + c + (h[i] - h[j])**2)
        # print(l, dp)
    return dp[n-1]

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

Submission status: Wrong Answer

Solution code:
def solve(n, c, h):
    dp = [float('inf')]*n
    dp[0] = 0
    def _val(newpos, pos):
        return dp[pos] + c + (h[newpos] - h[pos])**2
    for i in range(1, n):
        l, r = 0, i-1
        while l < r:
            mid = l + (r-l)//2
            if _val(i, mid) > _val(i, mid+1):
                l = mid + 1
            else:
                r = mid
        dp[i] = _val(i, l)
        # for j in range(i):
        #     dp[i] = min(dp[i], dp[j] + c + (h[i] - h[j])**2)
        # print(l, dp)
    return dp[n-1]

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

Submission status: Wrong Answer

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 = w, y
        I += 1
    r = u*h+v + h**2+C
    a, b = -2*h, r+h**2
    while J>1:
        (c, d), (e, f) = ls[J-1], ls[J-2]
        if (c-e)*(b-d) < (d-f)*(a-c):
            break
        J-=1
    J+=1
    ls[J] = (a, b)
print(r)

Submission status: Wrong Answer

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 abs(right - left) > 1:
            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: Wrong Answer

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:
                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: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
N, C = map(int, input().split())
h = list(map(int, input().split()))
dp = [0] * N
dp[1] = (h[1] - h[0]) ** 2 + C
for i in range(1, N):
  x0 = 0
  x1 = 0
  x2 = 0
  x3 = i - 1
  res = (h[i] - h[0]) ** 2 + C
  if x3 - x0 <= 2:
    for x in range(i):
      res = min(res, (h[i] - h[x]) ** 2 + C + dp[x])
  while x3 - x0 > 2:
    x1 = (x0 * 2 + x3) // 3
    x2 = (x0 + x3 * 2) // 3
    r1 = (h[i] - h[x1]) ** 2 + C + dp[x1]
    r2 = (h[i] - h[x2]) ** 2 + C + dp[x2]
    res = min(res, r1, r2)
    #print(i,x0,x3, r1,r2)
    if r1 < r2:
      x3 = x2
    else:
      x0 = x1
  for x in range(x0, x3 + 1): res = min(res, (h[i] - h[x]) ** 2 + C + dp[x])
  dp[i] = res
  #print(res, dp)
print(dp[-1])

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
N, C = map(int, input().split())
h = list(map(int, input().split()))
dp = [0] * N
dp[1] = (h[1] - h[0]) ** 2 + C
for i in range(1, N):
  x0 = 0
  x1 = 0
  x2 = 0
  x3 = i
  res = float("inf")
  if x3 - x0 <= 2:
    for x in range(i):
      res = min(res, (h[i] - h[x]) ** 2 + C + dp[x])
  while x3 - x0 > 2:
    x1 = (x0 * 2 + x3) // 3
    x2 = (x0 + x3 * 2) // 3
    r1 = (h[i] - h[x1]) ** 2 + C + dp[x1]
    r2 = (h[i] - h[x2]) ** 2 + C + dp[x2]
    res = min(res, r1, r2)
    if r1 < r2:
      x3 = x2
    else:
      x0 = x1
  dp[i] = res
  #print(res, dp)
print(dp[-1])

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:

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

dp = [0]*N
dp[0] = 0
for i in range(1,N): # O(N)
	l,r = -1,i-1
	while l+1<r: # O(logN)
		m = (l+r)//2
		lhs = dp[m+1]+(h[i]-h[m+1])**2
		rhs = dp[m+0]+(h[i]-h[m+0])**2
		if lhs<=rhs:
			l = m
		else:
			r = m
	dp[i] = dp[r]+(h[i]-h[r])**2+C

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

Submission status: Wrong Answer

Solution code:
N, C = map(int,input().split())
h = list(map(int,input().split()))
inf = 10 ** 13 + 7
dp = [inf] * N
dp[0] = 0
for i in range(N):
  if i != N - 1:
    temp = (h[i + 1] - h[i]) ** 2
  else:
    temp = 0
  for j in range(1, N - i):
    if (h[i + j] - h[i]) ** 2 - temp < C * j:
      dp[i + j] = min(dp[i + j], (h[i + j] - h[i]) ** 2 + dp[i] + C)
    else:
      if j != 1:
        break
#print(dp)
print(dp[N - 1])

Submission status: Wrong Answer

Solution code:

from Queue import deque


n, c = map(int, raw_input().split())
h = map(int, raw_input().split())
oo = (max(h) ** 2 + c) * n

dp = [0] * n
dp[0] = 0
lines = deque([(-2 * h[0], h[0] ** 2)])
for i in range(1, n):
    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) * (m2 - m2):
            lines.pop()
        else:
            break
    lines.append((mn, nn))
print(dp[n - 1])

Submission status: Wrong Answer

Solution code:


from Queue import deque


n, c = map(int, raw_input().split())
h = map(int, raw_input().split())
oo = (max(h) ** 2 + c) * n

dp = [oo] * n
dp[0] = 0
lines = deque([(-2 * h[0], h[0] ** 2)])
for i in range(1, n):
    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) * (m2 - m2):
            lines.pop()
        else:
            break
    lines.append((mn, nn))
print(dp[n - 1])

Submission status: Wrong Answer

Solution code:


from Queue import deque


n, c = map(int, raw_input().split())
h = map(int, raw_input().split())
oo = (max(h) ** 2 + c) * n

dp = [oo] * n
dp[n - 1] = 0
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 - n1) * (m2 - m1) >= (n1 - n2) * (m1 - mn):
            lines.popleft()
        else:
            break
    lines.append((mn, nn))
print(dp[0])

Submission status: Wrong Answer

Solution code:


from Queue import deque


n, c = map(int, raw_input().split())
h = map(int, raw_input().split())
oo = (max(h) ** 2 + c) * n

dp = [oo] * n
dp[n - 1] = 0
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 - n1) * (m2 - m1) > (n1 - n2) * (m1 - mn):
            lines.popleft()
        else:
            break
    lines.append((mn, nn))
print(dp[0])

Submission status: Wrong Answer

Solution code:


from Queue import deque


n, c = map(int, raw_input().split())
h = map(int, raw_input().split())
oo = (max(h) ** 2 + c) * n

dp = [oo] * n
dp[n - 1] = 0
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 - n1) * (m2 - m1) >= (n1 - n2) * (m1 - mn):
            lines.popleft()
        else:
            break
    lines.append((mn, nn))
print(dp[0])

Submission status: Wrong Answer

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
            break

print(dp[-1])

Submission status: Time Limit Exceeded

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()
A = IL()

dp = [0]

def cost(i,x):
  return dp[::-1][x] + (A[i+1+x]-A[i])**2 + C

def is_ok(i,mid1,mid2):
  if cost(i,mid1)>cost(i,mid2):
    return True
  else:
    return False

def meguru_bisect(i,ng, ok):
  if ok - ng == 2:
    return cost(i,ng+1)
  while (abs(ok - ng) > 2):
    mid1 = (ok*2 + ng) // 3
    mid2 = (ok + ng*2) // 3
    if is_ok(i,mid1,mid2):
      ok = mid1
    else:
      ng = mid2
  return min(cost(i,mid1),cost(i,mid2))

for i in range(N-1)[::-1]:
  dp.append(meguru_bisect(i,-1,N-1-i))

print(dp[-1])

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):
    vv = float("inf")
    bb = None
    while len(q)>=2 and q[-2][0]*h[i]+q[-2][1]<=q[-1][0]*h[i]+q[-1][1]:
        q.pop()
    for ii,item in enumerate(q):
        if item[0]*h[i]+item[1]<vv:
            vv = item[0]*h[i]+item[1]
            bb = ii
    for ii in range(len(q)-bb-1):
        q.pop()
#     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] = vv + 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:
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):
    vv = float("inf")
    bb = None
    for ii,item in enumerate(q):
        if item[0]*h[i]+item[1]<vv:
            vv = item[0]*h[i]+item[1]
            bb = ii
    for ii in range(len(q)-bb-1):
        q.pop()
#     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] = vv + 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)