Problem:


Score : 1000 points

Problem Statement

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 [i-1,i] and the horizontal range of [l_i,r_i], as shown in the following figure:

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.

Constraints

All input values are integers.

1≤N≤10^5

1≤l_i<r_i≤10^9

Partial Score

300 points will be awarded for passing the test set satisfying 1≤N≤400 and 1≤l_i<r_i≤400.

Input

The input is given from Standard Input in the following format:

N
l_1 r_1
l_2 r_2
:
l_N r_N

Output

Print the minimum cost to achieve connectivity.

Sample Input 1

3
1 3
5 7
1 3

Sample Output 1

2

The second rectangle should be moved to the left by a distance of 2.

Sample Input 2

3
2 5
4 6
1 4

Sample Output 2

0

The rectangles are already connected, and thus no move is needed.

Sample Input 3

5
999999999 1000000000
1 2
314 315
500000 500001
999999999 1000000000

Sample Output 3

1999999680

Sample Input 4

5
123456 789012
123 456
12 345678901
123456 789012
1 23

Sample Output 4

246433

Sample Input 5

1
1 400

Sample Output 5

0



Sample input:
3
1 3
5 7
1 3


Sample output:
2

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
from heapq import heappop, heappush

"""
f(x) = （一番上の長方形の左端がxに来るときのコストの最小値） を関数ごと更新していきたい
更新後をg(x)とする
g(x) = |x-L| + min_{-width_1 \leq t\leq width_2} f(x+t), 前回の幅、今回の幅
常に、区間上で最小値を持ち傾きが1ずつ変わる凸な関数であることが維持される。（区間は1点かも）
傾きが変わる点の集合S_f = S_f_lower + S_f_upperを持っていく。
S_f_lower, S_upperは一斉に定数を足す：変化量のみ持つ
"""

N = int(input())
LR = [[int(x) for x in input().split()] for _ in range(N)]

# initialize
L,R = LR[0]
S_lower = [-L]
S_upper = [L]
min_f = 0
add_lower = 0
add_upper = 0
prev_w = R - L

push_L = lambda x: heappush(S_lower, -x)
push_R = lambda x: heappush(S_upper, x)
pop_L = lambda: -heappop(S_lower)
pop_R = lambda: heappop(S_upper)

for L,R in LR[1:]:
    w = R - L
    # 平行移動とのminをとるステップ
    add_lower -= w
    add_upper += prev_w
    # abs(x-L) を加えるステップ
    # abs は瞬間に2傾きが変わるので
    x = pop_L() + add_lower
    y = pop_R() + add_upper
    x,y,z,w = sorted([x,y,L,L])
    push_L(x - add_lower)
    push_L(y - add_lower)
    push_R(z - add_upper)
    push_R(w - add_upper)
    min_f += z-y

print(min_f)

Submission status: Wrong Answer

Solution code:
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[0]-i)
    if i < l[0]:
         d = l[0] - i
    elif r[0] < i: 
         d = i - r[0]
    else: 
         d = 0
    dp[0][i] = d
    
for ni in range(1,n): # 何段目で?
    for xj in range(N): # どこに接地させる?
        # このブロックをxjに持っていくコスト
        if xj < l[ni]: 
            d = l[ni] - xj
        elif r[ni] < xj:
            d = xj - r[ni]
        else: 
            d = 0 
        # 前のブロックで、xjに設置している中で最もコストの低いものに、今回のコストを加える
        min_cost = 1000
        for xk in range(N):
            if dp[ni-1][xj] > 400: continue
            min_cost = min(min_cost, dp[ni-1][xj])
        dp[ni][xj] = min_cost+d

print(min(dp[n-1]))

Submission status: Wrong Answer

Solution code:
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[0]-i)
    if i < l[0]:
         d = l[0] - i
    elif r[0] < i: 
         d = i - r[0]
    else: 
         d = 0
    dp[0][i] = d
    
for ni in range(1,n): # 何段目で?
    for xj in range(N): # どこに接地させる?
        # このブロックをxjに持っていくコスト
        if xj < l[ni]: 
            d = l[ni] - xj
        elif r[ni] < xj:
            d = xj - r[ni]
        else: 
            d = 0 
        # 前のブロックで、xjに設置している中で最もコストの低いものに、今回のコストを加える
        min_cost = 1000
        for xk in range(N):
            min_cost = min(min_cost, dp[ni-1][xj])
        dp[ni][xj] = min_cost+d
print(min(dp[n-1]))

Submission status: Wrong Answer

Solution code:
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[0]-i)
    if i < l[0]:
         d = l[0] - i
    elif r[0] < i: 
         d = i - r[0]
    else: 
         d = 0
    dp[0][i] = d
    
for ni in range(1,n): # 何段目で?
    for xj in range(N): # どこに接地させる?
        # このブロックをxjに持っていくコスト
        if xj < l[ni]: 
            d = l[ni] - xj
        elif r[ni] < xj:
            d = xj - r[ni]
        else: 
            d = 0 
        # 前のブロックで、xjに設置している中で最もコストの低いものに、今回のコストを加える
        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]))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
n = int(input())

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

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

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

# 一番上のブロックを動かした時のコスト
for i in range(400):
    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(400):
        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]))

Submission status: Wrong Answer

Solution code:
n = int(input())
a = [list(map(int,input().split())) for i in range(n)]
dp = [[float("inf")]*(500) for i in range(n+1)]
if n > 400:
  exit()
for i in range(500):
  dp[0][i] = 0
for i in range(1,n+1):
  m = a[i-1][1] - a[i-1][0]
  mm = a[i-2][1] - a[i-2][0]
  for j in range(405):
    for k in range(405):
      if (j<= k and k<=j+m) or (k<= j and j <= k+mm) or i == 1:
        dp[i][j] = min(dp[i][j],dp[i-1][k]+abs(j-a[i-1][0]))
ans = float("inf")
for i in range(500):
  ans = min(ans,dp[n][i])
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = [list(map(int,input().split())) for i in range(n)]
def keisan(x):
  ans = 0
  for i,j in a:
    if x < i:
      ans += i-x
    elif x > j:
      ans += x-j
  return ans
x0 = 0
x3 = 1<<32
while x3 - x0 >2:
  x1 = (x0*2+x3)//3
  x2 =  (x0+x3*2)//3
  y1 = keisan(x1)
  y2 = keisan(x2)
  if y1 > y2:
    x0 = x1
  else:
    x3 = x2
print(min(keisan(x0),keisan(x0+1),keisan(x0+2)))

Submission status: Wrong Answer

Solution code:
# seishin.py
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

def debug(L, s, t, R):
    L0 = L[:]
    Q1 = []; Q2 = []
    while L0:
        Q1.append(-s-heappop(L0))
    R0 = R[:]
    while R0:
        Q2.append(t+heappop(R0))
    print("debug:", *Q1[::-1]+Q2)


#print(L, s, t, R)
res = 0
for i in range(N-1):
    l0, r0 = P[i]
    l1, r1 = P[i+1]
    #print(">", l1, r1)
    s += (r1 - l1); t += (r0 - l0)
    if -s-L[0] <= l1-1 <= t+R[0]:
        #print(0)
        heappush(L, -l1+1-s)
        heappush(R, l1-1-t)
        # res += 0
    elif l1-1 < -s-L[0]:
        #print(1)
        heappush(L, -l1+1-s)
        heappush(L, -l1+1-s)
        p = -heappop(L)-s
        d = p - (-L[0]-s)
        heappush(R, p-t)
        #print(d)
        if d == 0:
            res += p - (l1-1)
        else:
            res += d
    elif t+R[0] < l1-1:
        #print(2)
        heappush(R, l1-1-t)
        heappush(R, l1-1-t)
        p = heappop(R) + t
        d = R[0]+t - p
        heappush(L, -p-s)
        #print(d)
        if d == 0:
            res += (l1-1) - p
        else:
            res += d
    #print(L, s, t, R, -s-L[0], R[0]+t, res)
    #debug(L, s, t, R)
print(res)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
num_lec = int(input())
l_lec = [list(map(int, input().split())) for i in range(num_lec)]

l_set = set([])
for lec in l_lec:
    l_set.add(lec[0])
    l_set.add(lec[1])

all_dis = []
for num in l_set:
    l_dis = []
    for lec in l_lec:
        if lec[0] <= num <= lec[1]:
            min_dis = 0
        else:
            dis_0 = num - lec[0]
            if dis_0 < 0:
                dis_0 *= -1
            dis_1 = num - lec[1]
            if dis_1 < 0:
                dis_1 *= -1
            if dis_0 > dis_1:
                min_dis = dis_1
            else:
                min_dis = dis_0
        l_dis.append(min_dis)
    sum_dis = sum(l_dis)
    all_dis.append(sum_dis)

ans = min(all_dis)

print(ans)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
num_lec = int(input())
l_lec = [list(map(int, input().split())) for i in range(num_lec)]

sum_lec_right = [lec[1] for lec in l_lec]
sum_lec_left = [lec[0] for lec in l_lec]

# print(sum_lec_right)
# print(sum_lec_left)

# min_sum = min(sum_lec_left)
max_sum = max(sum_lec_right)


def make_dis(poi_o, lec):
    dis = 0
    if poi_o < lec[0]:
        dis = lec[0] - poi_o
    elif lec[0] <= poi_o <= lec[1]:
        dis = 0
    elif lec[1] < poi_o:
        dis = poi_o - lec[1]
    return dis


l_dis = []
for poi_o in range(0, max_sum + 1):
    sum_dis = 0
    for lec in l_lec:
        dis = make_dis(poi_o, lec)
        sum_dis += dis
    l_dis.append(sum_dis)

# print(l_dis)

ans = min(l_dis)
print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Accepted

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

from heapq import heappush, heappushpop

"""
・f(x) = （最上段の左端座標） -> 最小コスト
・g = newf とすると、g(x) = |x-l| + min_{x-w_{n-1}<=y<=x+w_n}f(y)
・常に [A0,B0] 上で定数、[A_i,A_{i-1}]で傾き-i、[B_{i-1},B_i]で傾きiの下に凸な折れ線
heapqで(A,B)の形で関数を持つ
・1段目の長方形で、A = [l], B = [l] からスタート（f(x) = |x - l|）
"""

N = int(readline())
m = map(int,read().split())
L,R = zip(*zip(m,m))

A = [-L[0]]; B = [L[0]]
addA = 0
addB = 0
min_f = 0
for n in range(1,N):
    p = R[n-1] - L[n-1]; q = R[n] - L[n]
    # まず、f(x) = min_{x-p <= y <= x+q} f(y) へと更新
    addA += (-q); addB += p
    a = -A[0] + addA
    b = B[0] + addB
    x = L[n]
    # x で座標を2回切り替えるようにする
    if x <= a:
        # 左に2つ入れたあと、右に1つうつす
        min_f += a - x
        heappush(A,-x + addA)
        y = -heappushpop(A,-x + addA) + addA
        heappush(B, y - addB)
    elif x >= b:
        # 右に2つ入れたあと、左に1つうつす
        min_f += x - b
        heappush(B, x - addB)
        y = heappushpop(B, x - addB) + addB
        heappush(A, -y + addA)
    else:
        # 左右に1つずつ入れる
        heappush(A, -x + addA)
        heappush(B, x - addB)

print(min_f)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from heapq import heappop, heappush

"""
f(x) = （一番上の長方形の左端がxに来るときのコストの最小値） を関数ごと更新していきたい
更新後をg(x)とする
g(x) = |x-L| + min_{-width_1 \leq t\leq width_2} f(x+t), 前回の幅、今回の幅
常に、区間上で最小値を持ち傾きが1ずつ変わる凸な関数であることが維持される。（区間は1点かも）
傾きが変わる点の集合S_f = S_f_lower + S_f_upperを持っていく。
S_f_lower, S_upperは一斉に定数を足す：変化量のみ持つ
"""

N = int(input())
LR = [[int(x) for x in input().split()] for _ in range(N)]

# initialize
L,R = LR[0]
S_lower = [-L]
S_upper = [L]
min_f = 0
add_lower = 0
add_upper = 0
prev_w = R - L

push_L = lambda x: heappush(S_lower, -x)
push_R = lambda x: heappush(S_upper, x)
pop_L = lambda: -heappop(S_lower)
pop_R = lambda: heappop(S_upper)

for L,R in LR[1:]:
    w = R - L
    # 平行移動とのminをとるステップ
    add_lower -= w
    add_upper += prev_w
    # abs(x-L) を加えるステップ
    # abs は瞬間に2傾きが変わるので
    x = pop_L() + add_lower
    y = pop_R() + add_upper
    a,b,c,d = sorted([x,y,L,L])
    push_L(a - add_lower)
    push_L(b - add_lower)
    push_R(c - add_upper)
    push_R(d - add_upper)
    min_f += c-b
    prev_w = w

print(min_f)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# seishin.py
N = int(input())
P = [list(map(int, input().split())) for i in range(N)]

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)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# seishin.py
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

def debug(L, s, t, R):
    L0 = L[:]
    Q1 = []; Q2 = []
    while L0:
        Q1.append(-s-heappop(L0))
    R0 = R[:]
    while R0:
        Q2.append(t+heappop(R0))
    print("debug:", *Q1[::-1]+Q2)


#print(L, s, t, R)
res = 0
for i in range(N-1):
    l0, r0 = P[i]
    l1, r1 = P[i+1]
    #print(">", l1, r1)
    s += (r1 - l1); t += (r0 - l0)
    if -s-L[0] <= l1-1 <= t+R[0]:
        #print(0)
        heappush(L, -l1+1-s)
        heappush(R, l1-1-t)
        # res += 0
    elif l1-1 < -s-L[0]:
        #print(1)
        heappush(L, -l1+1-s)
        heappush(L, -l1+1-s)
        p = -heappop(L)-s
        #d = (-L[0]-s) - p
        heappush(R, p-t)
        #print(d)
        #res += d
        res += (p - (l1-1))
    elif t+R[0] < l1-1:
        #print(2)
        heappush(R, l1-1-t)
        heappush(R, l1-1-t)
        p = heappop(R) + t
        #d = R[0]+t - p
        heappush(L, -p-s)
        #print(d)
        res += (l1-1 - p)
    #print(L, s, t, R, -s-L[0], R[0]+t, res)
    #debug(L, s, t, R)
print(res)

Submission status: Runtime Error

Solution code:
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): # どこに接地させる?
        # このブロックをxjに持っていくコスト
        if xj < l[ni]: 
            d = l[ni] - xj
        elif r[ni] < xj:
            d = xj - r[ni]
        else: 
            d = 0 
        # 前のブロックで、xjに設置している中で最もコストの低いものに、今回のコストを加える
        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]))

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
N = int(input())
P = [list(map(int, input().split())) for i in range(N)]

INF = 10**18

L = max(r for l, r in P)
S = [0]*L
l0, r0 = P[0]
for i in range(L):
    S[i] = abs(i - (l0-1))
for i in range(N-1):
    l0, r0 = P[i]
    l1, r1 = P[i+1]
    T = [0]*L
    for x in range(L):
        r = INF
        for y in range(max(0, x-(r0-l0)), min(L, x+(r1-l1)+1)):
            r = min(r, S[y])
        T[x] = abs(x-(l1-1)) + r
    S = T
print(min(S))

Submission status: Runtime Error

Solution code:
def solve(N, lefts, rights):
    assert 1 <= N <= 400
    min_l, max_l = min(lefts), max(lefts)
    max_r = max(rights)
    assert 1 <= min_l < max_r <= 400
    dp = [[float("inf")] * (max_l + 1) for _ in range(N)]
    dp = [[0] * (max_l + 1)] + dp
    lefts = (1,) + lefts
    rights = (max_l,) + rights
    for i in range(1, N+1):
        pre_length = rights[i-1] - lefts[i-1]
        for l in range(1, max_l + 1):
            #print("{}, [{}, {}]".format(l, max(1, l-pre_length), l))
            dp[i][l] = min(dp[i-1][max(1, l-pre_length):min(rights[i]+1, max_l+1)] or [float("inf")]) + abs(lefts[i]-l)
        #print(dp[i])
    return(min(dp[-1][1:]))


if __name__ == "__main__":
    N = int(input())
    lr = [[int(i) for i in input().split()] for _ in range(N)]
    lefts, rights = zip(*lr)
    print(solve(N, lefts, rights))

Submission status: Runtime Error

Solution code:
def solve(N, lefts, rights):
    assert 1 <= N <= 400
    min_l, max_l = min(lefts), max(lefts)
    max_r = max(rights)
    assert 1 <= min_l < max_r <= 400
    dp = [[float("inf")] * (max_l + 1) for _ in range(N)]
    dp = [[0] * (max_l + 1)] + dp
    lefts = (1,) + lefts
    rights = (max_l,) + rights
    for i in range(1, N+1):
        pre_length = rights[i-1] - lefts[i-1]
        for l in range(1, max_l + 1):
            #print("{}, [{}, {}]".format(l, max(1, l-pre_length), l))
            dp[i][l] = min(dp[i-1][max(1, l-pre_length):min(rights[i]+1, max_l+1)], default=float("inf")) + abs(lefts[i]-l)
        #print(dp[i])
    return(min(dp[-1][1:]))


if __name__ == "__main__":
    N = int(input())
    lr = [[int(i) for i in input().split()] for _ in range(N)]
    lefts, rights = zip(*lr)
    print(solve(N, lefts, rights))

Submission status: Runtime Error

Solution code:
def solve(N, lefts, rights):
    assert 1 <= N <= 400
    min_l, max_l = min(lefts), max(lefts)
    max_r = max(rights)
    assert 1 <= min_l < max_r <= 400
    dp = [[float("inf")] * (max_l + 1) for _ in range(N)]
    dp = [[0] * (max_l + 1)] + dp
    lefts = (1,) + lefts
    rights = (max_l,) + rights
    for i in range(1, N+1):
        pre_length = rights[i-1] - lefts[i-1]
        for l in range(1, max_l + 1):
            #print("{}, [{}, {}]".format(l, max(1, l-pre_length), l))
            dp[i][l] = min(dp[i-1][max(1, l-pre_length):min(rights[i]+1, max_l+1)], default=float("inf")) + abs(lefts[i]-l)
        #print(dp[i])
    return(min(dp[-1][1:]))


if __name__ == "__main__":
    N = int(input())
    lr = [[int(i) for i in input().split()] for _ in range(N)]
    lefts, rights = zip(*lr)
    print(solve(N, lefts, rights))