Submission #4034724

---

Source Code Expand

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 Info

Judge Result