Problem: AtCoDeer the deer found N rectangle lying on the table, each with height 1. If we consider the surface of the desk as a two-dimensional plane, the i-th rectangle i(1≤i≤N) covers the vertical range of   AtCoDeer will move these rectangles horizontally so that all the rectangles are connected. For each rectangle, the cost to move it horizontally by a distance of x, is x. Find the minimum cost to achieve connectivity. It can be proved that this value is always an integer under the constraints of the problem.

Submission attempts (in order):
n = int(input())

l = [0]*n
r = [0]*n

for i in range(n):
    l[i], r[i] = list(map(int, input().split()))

N = 10**9+1
dp = [[0 for i in range(N)] for j in range(n)]


for i in range(N):
    if r[0] < i: d = i-r[0]
    elif i < l[0]: d = l[0]-i
    else: d = 0
    dp[0][i] = d


for ni in range(1,n):
    for i in range(N):
        if r[ni] < i: d = i-r[ni]
        elif i < l[ni]: d = l[ni]-i
        else: d = 0
        dp[ni][i] = d + dp[ni-1][i]
print(min(dp[n-1]))

import math
n = int(input())
N = 400
if n > N: exit()

l = [0]*n
r = [0]*n
for i in range(n): 
    l[i], r[i] = list(map(int, input().split()))
dp = [[1000 for i in range(N)] for j in range(n)]

for i in range(N): 
    dp[0][i] = abs(l[ni]-i)
    if i < l[ni]: 
         d = l[ni] - i
    elif r[ni] < i: 
         d = i - r[ni]
    else: 
         d = 0
    dp[0][i] = d
    
for ni in range(1,n): 
    for xj in range(N): 
        
        if xj < l[ni]: 
            d = l[ni] - xj
        elif r[ni] < xj:
            d = xj - r[ni]
        else: 
            d = 0 
        
        min_cost = 1000
        for xk in range(N):
            d2 =  0
            if xk < xj:
                if xj <= xk+r[ni-1]:
                    min_cost = min(min_cost, dp[ni-1][xj] + d2 )
            elif xj < xk:
                if xk <= xj+r[ni]:
                    min_cost = min(min_cost, dp[ni-1][xj] + d2 ) 
            else:
                min_cost = min(min_cost, dp[ni-1][xj] + d2)
        dp[ni][xj] = min_cost+d
print(min(dp[n-1]))

n = int(input())

if n>400: exit()

l = [0]*n
r = [0]*n

for i in range(n):
    l[i], r[i] = list(map(int, input().split()))

N = 400+1
dp = [[0 for i in range(N)] for j in range(n)]


for i in range(N):
    if r[0] < i: d = i-r[0]
    elif i < l[0]: d = l[0]-i
    else: d = 0
    dp[0][i] = d


for ni in range(1,n+1):
    for i in range(N):
        if r[ni] < i: d = i-r[ni]
        elif i < l[ni]: d = l[ni]-i
        else: d = 0
        dp[ni][i] = d + dp[ni-1][i]
print(min(dp[n-1]))

N = int(input())
P = [list(map(int, input().split())) for i in range(N)]
 
INF = 10**18
 
from heapq import heappush, heappop
 
l0, r0 = P[0]
 
L = [-l0+1]
R = [l0-1]
s = t = 0
 
res = 0
for i in range(N-1):
    l0, r0 = P[i]
    l1, r1 = P[i+1]
    s += (r1 - l1); t += (r0 - l0)
    if -s-L[0] <= l1-1 <= t+R[0]:
        heappush(L, -l1+1-s)
        heappush(R, l1-1-t)
    elif l1-1 < -s-L[0]:
        heappush(L, -l1+1-s)
        heappush(L, -l1+1-s)
        p = -heappop(L)-s
        heappush(R, p-t)
        res += (p - (l1-1))
    elif t+R[0] < l1-1:
        heappush(R, l1-1-t)
        heappush(R, l1-1-t)
        p = heappop(R) + t
        heappush(L, -p-s)
        res += (l1-1 - p)
print(res)

Verdicts: Time Limit Exceeded

Runtime Error

Runtime Error

Accepted