Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
import sys
N,k=map(int,input())
l=[int(x) for x in input().split()]
l1=[sys.maxsize]*(N)
l1[0]=0
for i in range(N):
    for j in range(i+1,i+k+1):
        if j<N:
            l1[j]=min(l1[j],l1[i]+abs(l[j]-l[i]))
print(l1[N-1])
        


Fixed submission:
import sys
N,k=map(int,input().split())
l=[int(x) for x in input().split()]
l1=[sys.maxsize]*(N)
l1[0]=0
for i in range(N):
    for j in range(i+1,i+k+1):
        if j<N:
            l1[j]=min(l1[j],l1[i]+abs(l[j]-l[i]))
print(l1[N-1])

Buggy python submission (verdict: Time Limit Exceeded):
import sys
N,k=map(int,input().split())
l=[int(x) for x in input().split()]
l1=[sys.maxsize]*(N)
l1[0]=0
for i in range(N):
    for j in range(i+1,i+k+1):
        if j<N:
            l1[j]=min(l1[j],l1[i]+abs(l[j]-l[i]))
print(l1[N-1])
        


Fixed submission:
import sys
N,k=map(int,input().split())
l=[int(x) for x in input().split()]
l1=[sys.maxsize]*(N)
l1[0]=0
for i in range(N):
    for j in range(i+1,i+k+1):
        if j<N:
            l1[j]=min(l1[j],l1[i]+abs(l[j]-l[i]))
print(l1[N-1])

Buggy python submission (verdict: Runtime Error):
import sys
N,k=map(int,input())
l=[int(x) for x in input().split()]
l1=[sys.maxsize]*(N)
l1[0]=0
for i in range(N):
    for j in range(i+1,i+k+1):
        if j<N:
            l1[j]=min(l1[j],l1[i]+abs(l[j]-l[i]))
print(l1[N-1])
        


Fixed submission:
import sys
N,k=map(int,input().split())
l=[int(x) for x in input().split()]
l1=[sys.maxsize]*(N)
l1[0]=0
for i in range(N):
    for j in range(i+1,i+k+1):
        if j<N:
            l1[j]=min(l1[j],l1[i]+abs(l[j]-l[i]))
print(l1[N-1])

Buggy python submission (verdict: Runtime Error):
import sys
N=int(input())
l=[int(x) for x in input().split()]
l1=[sys.maxsize]*(N+1)
l1[0]=0
for i in range(N):
    for j in range(i+1,i+k+1):
        if j<N:
            l1[j]=min(l1[j],l1[i]+abs(l[j]-l[i]))
print(l1[N-1])
        


Fixed submission:
import sys
N,k=map(int,input().split())
l=[int(x) for x in input().split()]
l1=[sys.maxsize]*(N)
l1[0]=0
for i in range(N):
    for j in range(i+1,i+k+1):
        if j<N:
            l1[j]=min(l1[j],l1[i]+abs(l[j]-l[i]))
print(l1[N-1])
Buggy python submission (verdict: Time Limit Exceeded):
N=int(input())
l1=[[] for i in range(N)]
for i in range(N):
    l=list(map(int,input().split()))
    for j in range(len(l)):
        l1[i].append(l[j])
pos=-1
f=-1
suma=0
for i in range(N):
    f=i
    if l1[i][0]>=l1[i][1] and l1[i][0]>=l1[i][2]:
        s=l1[i][0]
       # print(s)
        pos=0
    elif l1[i][1]>=l1[i][0] and l1[i][1]>=l1[i][2]:
        s=l1[i][1]
       # print(s)
        pos=1
    else:
        s=l1[i][2]
       # print(s)
        pos=2
    m=pos
    for j in range(i-1,-1,-1):
        if m==0:
            if l1[j][1]>=l1[j][2]:
                s=s+l1[j][1]
                #print(l1[j][1])
                m=1
            else:
                s=s+l1[j][2]
                #print(l1[j][2])
                m=2
        elif m==1:
            if l1[j][0]>=l1[j][2]:
                s=s+l1[j][0]
                #print(l1[j][0])
                m=0
            else:
                s=s+l1[j][2]
                #print(l1[j][2])
                m=2
        else:
            if l1[j][0]>=l1[j][1]:
                s=s+l1[j][0]
                #print(l1[j][0])
                m=0
            else:
                s=s+l1[j][1]
                #print(l1[j][1])
                m=1
    if suma<s:
        suma=s
    for j in range(i+1,N):
        if pos==0:
            if l1[j][1]>=l1[j][2]:
                s=s+l1[j][1]
                #print(l1[j][1])
                pos=1
            else:
                s=s+l1[j][2]
                #print(l1[j][2])
                pos=2
        elif pos==1:
            if l1[j][0]>=l1[j][2]:
                s=s+l1[j][0]
                #print(l1[j][0])
                pos=0
            else:
                s=s+l1[j][2]
                #print(l1[j][2])
                pos=2
        else:
            if l1[j][0]>=l1[j][1]:
                s=s+l1[j][0]
                #print(l1[j][0])
                pos=0
            else:
                s=s+l1[j][1]
                #print(l1[j][1])
                pos=1
    #print(s)
    if suma<s:
        suma=s
print(suma)


Fixed submission:
N=int(input())
l1=[[] for i in range(N)]
for i in range(N):
    l=list(map(int,input().split()))
    for j in range(len(l)):
        l1[i].append(l[j])
l2=[[] for i in range(N)]
for j in l1[0]:
    l2[0].append(j)
for j in range(1,N):
    l2[j].append(l1[j][0]+max(l2[j-1][1],l2[j-1][2]))
    l2[j].append(l1[j][1]+max(l2[j-1][0],l2[j-1][2]))
    l2[j].append(l1[j][2]+max(l2[j-1][0],l2[j-1][1]))
#print(l2)
print(max(l2[N-1][0],l2[N-1][1],l2[N-1][2]))
Buggy python submission (verdict: Runtime Error):
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**8)
n,k=map(int,input().split())
z=list(map(int,input().split()))
dp=[0 for i in range(len(z))]
vi=[0 for i in range(len(z))]
def dps(i,dp,vi):
    if(i<=0):
        return 0;
    if(vi[i]==1):
        return dp[i];
    
    vi[i]=1
    maxa=98778979878
    for j in range(1,min(i+1,k+1)):
        maxa=min((dps(i-j,dp,vi)+abs(z[i]-z[i-j])),maxa)
    dp[i]=maxa
    return dp[i];
print(dps(len(z)-1,dp,vi))



Fixed submission:
import sys
input=sys.stdin.readline
a=int(input())
ans=[]
total=0
for i in range(a):
    z=list(map(int,input().split()))
    ans.append(z)
for i in range(a):
    if(i==0):
        t1=ans[0][0]
        t2=ans[0][1]
        t3=ans[0][2]
        
    else:
        x1=t1
        x2=t2
        x3=t3
        t1=max(x2,x3)+ans[i][0]
        t2=max(x1,x3)+ans[i][1]
        t3=max(x1,x2)+ans[i][2]
        
    
print(max(t1,t2,t3))
Buggy python submission (verdict: Runtime Error):
	def rr(): return input().rstrip()
def rri(): return int(rr())
def rrl(): return list(map(int, rr().split()))
def rrt(): return tuple(map(int, rr().split()))
from collections import defaultdict
def mus(d=lambda: 0): return defaultdict(lambda: defaultdict(d))
def dd0(d=lambda: 0): return defaultdict(d)
def ms(x, y, d=0): return [[0]*y for i in range(x)]
def ar(x, d=0): return [d]*x
def ppm(m, n=0, x=0, y=0): print("\n".join(("\t".join((str(m[j][i]) for j in range(y or n))) for i in range(x or n))))
def ppa(a, n): print("\t".join(map(str, a[0:n])))
def ppl(a=0, x=[1]): x[0]=a or (x[0]+1); print("-"+"- -"*14+"-# "+str(x[0]-2)+" #-"+"- -"*14+"-")
def fltn(a): (i for sub in a for i in sub)
def yn(x): return "YES" if x else "NO"
from itertools import accumulate
from itertools import groupby
def grp(x): return ((i, sum(1 for _ in g)) for i, g in groupby(x))
import math
def rnar(): return (*rrl(), rrl())
def rn(): return (*rrl(),)
def dpp(a, b=""): print("[{}]o[{}]".format(a, b))

def read():
    return rnar()
    return (0,)

def solve(n, arr):
    dp = ar(n)
    dp[0] = 0
    dp[1] = abs(arr[1]-arr[0])
    for i in range(2, n):
        dp[i] = min(dp[i-1] + abs(arr[i-1]-arr[i]), dp[i-2] + abs(arr[i-2]-arr[i]))

    ans = dp[-1]
    return ans

if __name__ == "__main__":
    #test_count = rri()
    test_count = 1
    for _ in range(test_count):
        input_data = read()
        result = solve(*input_data)
        print(result)


Fixed submission:
def rr(): return input().rstrip()
def rri(): return int(rr())
def rrl(): return list(map(int, rr().split()))
def rrt(): return tuple(map(int, rr().split()))
from collections import defaultdict
def mus(d=lambda: 0): return defaultdict(lambda: defaultdict(d))
def dd0(d=lambda: 0): return defaultdict(d)
def ms(x, y, d=0): return [[0]*y for i in range(x)]
def ar(x, d=0): return [d]*x
def ppm(m, n=0, x=0, y=0): print("\n".join(("\t".join((str(m[j][i]) for j in range(y or n))) for i in range(x or n))))
def ppa(a, n): print("\t".join(map(str, a[0:n])))
def ppl(a=0, x=[1]): x[0]=a or (x[0]+1); print("-"+"- -"*14+"-# "+str(x[0]-2)+" #-"+"- -"*14+"-")
def fltn(a): (i for sub in a for i in sub)
def yn(x): return "YES" if x else "NO"
from itertools import accumulate
from itertools import groupby
def grp(x): return ((i, sum(1 for _ in g)) for i, g in groupby(x))
import math
#def rnar(): return (*rrl(), rrl())
#def rn(): return (*rrl(),)
def dpp(a, b=""): print("[{}]o[{}]".format(a, b))

def read():
    return (rri(), rrl())
    return (0,)

def solve(n, arr):
    dp = ar(n)
    dp[0] = 0
    dp[1] = abs(arr[1]-arr[0])
    for i in range(2, n):
        dp[i] = min(dp[i-1] + abs(arr[i-1]-arr[i]), dp[i-2] + abs(arr[i-2]-arr[i]))

    ans = dp[-1]
    return ans

if __name__ == "__main__":
    #test_count = rri()
    test_count = 1
    for _ in range(test_count):
        input_data = read()
        result = solve(*input_data)
        print(result)
Buggy python submission (verdict: Time Limit Exceeded):
n, k = map(int, input().split())
hs = list(map(int, input().split()))
dp = [float('inf')] * n
dp[0] = 0
for i in range(1, n):
  pre = min(i, k)
  while pre > 0:
    dp[i] = min(dp[i], dp[i-pre] + abs(hs[i-pre] - hs[i]))
    pre -= 1
print(dp[-1])

Fixed submission:
n, k = map(int, input().split())
hs = list(map(int, input().split()))
dp = [float('inf')] * n
dp[0] = 0
for i in range(1, n):
  pre = min(i, k)
  while pre > 0:
    dp[i] = min(dp[i], dp[i-pre] + abs(hs[i-pre] - hs[i]))
    pre -= 1
print(dp[-1])

Buggy python submission (verdict: Runtime Error):
n, k = map(int, input().split())
hs = list(map(int, input().split()))
dp = [0] * float('inf')
dp[0] = 0
for i in range(1, n):
  pre = min(i, k)
  while pre > 0:
    dp[i] = min(dp[i], dp[i-pre] + abs(hs[i-pre] - hs[i]))
    pre -= 1
print(dp[-1])

Fixed submission:
n, k = map(int, input().split())
hs = list(map(int, input().split()))
dp = [float('inf')] * n
dp[0] = 0
for i in range(1, n):
  pre = min(i, k)
  while pre > 0:
    dp[i] = min(dp[i], dp[i-pre] + abs(hs[i-pre] - hs[i]))
    pre -= 1
print(dp[-1])

Buggy python submission (verdict: Runtime Error):
n, k = [int(c) for c in input().split()]
hs = [int(c) for c in input().split()]
dp = [0] * n
for i in range(1, n):
  dp[i] = 0
  pre = min(i, k)
  while pre > 0:
   	dp[i] = min(dp[i], dp[i-pre] + abs(hs[i-pre] - hs[i]))
    pre -= 1
print(dp[-1])


Fixed submission:
n, k = map(int, input().split())
hs = list(map(int, input().split()))
dp = [float('inf')] * n
dp[0] = 0
for i in range(1, n):
  pre = min(i, k)
  while pre > 0:
    dp[i] = min(dp[i], dp[i-pre] + abs(hs[i-pre] - hs[i]))
    pre -= 1
print(dp[-1])
Buggy python submission (verdict: Runtime Error):
from functools import lru_cache

N = int(input())
heights = [int(h) for h in input().split()]

# 记忆化
@lru_cache(None)
def dfs(i):
    if i == len(heights) - 1:
        return 0
    return min(abs(heights[i] - heights[i + 1]) + dfs(i + 1) if i + 1 < len(heights) else float("inf"),

               abs(heights[i] - heights[i + 2]) + dfs(i + 2) if i + 2 < len(heights) else float("inf"))


print(dfs(0))


Fixed submission:
from functools import lru_cache
import sys
sys.setrecursionlimit(20000000)
N = int(input())
heights = [int(h) for h in input().split()]


# heights = [10, 30, 40, 20]

# heights = [10, 10]
# heights = [30, 10, 60, 10, 60, 50]
# 记忆化
@lru_cache(None)
def dfs(i):
    if i == len(heights) - 1:
        return 0
    return min(abs(heights[i] - heights[i + 1]) + dfs(i + 1) if i + 1 < len(heights) else float("inf"),

               abs(heights[i] - heights[i + 2]) + dfs(i + 2) if i + 2 < len(heights) else float("inf"))


print(dfs(0))

Buggy python submission (verdict: Runtime Error):
from functools import lru_cache
N = int(input())
heights = [int(h) for h in input().split()]

# 记忆化
@lru_cache(None)
def dfs(i):
    if i == len(heights) - 1:
        return 0
    if i >= len(heights):
        return float("inf")

    return min(abs(heights[i] - heights[i + 1]) + dfs(i + 1) if i + 1 < len(heights) else float("inf"),

               abs(heights[i] - heights[i + 2]) + dfs(i + 2) if i + 2 < len(heights) else float("inf"))

print(dfs(0))

Fixed submission:
from functools import lru_cache
import sys
sys.setrecursionlimit(20000000)
N = int(input())
heights = [int(h) for h in input().split()]


# heights = [10, 30, 40, 20]

# heights = [10, 10]
# heights = [30, 10, 60, 10, 60, 50]
# 记忆化
@lru_cache(None)
def dfs(i):
    if i == len(heights) - 1:
        return 0
    return min(abs(heights[i] - heights[i + 1]) + dfs(i + 1) if i + 1 < len(heights) else float("inf"),

               abs(heights[i] - heights[i + 2]) + dfs(i + 2) if i + 2 < len(heights) else float("inf"))


print(dfs(0))
Buggy python submission (verdict: Runtime Error):
n, nums = input().split()
print(n, nums)

Fixed submission:
n = int(input())
nums = list(map(int, input().split()))
if n == 1:
  print(0)
dp = [0 for _ in range(n)]
dp[0] = 0
dp[1] = abs(nums[1]-nums[0])

for i in range(2, n):
  dp[i] = min(dp[i-1] + abs(nums[i] - nums[i-1]), dp[i-2]+abs(nums[i]-nums[i-2]))

print(dp[-1])
Buggy python submission (verdict: Time Limit Exceeded):
n, k = list(map(int, input().split()))
nums = list(map(int, input().split()))
 
dp = [float('inf') for _ in range(n)]
dp[0] = 0
 
for i in range(1, n):
  for j in range(max(0, i-k), i):
    dp[i] = min(dp[i], dp[j] + abs(nums[i]-nums[j]))
print(dp[-1])

Fixed submission:
n, k = list(map(int, input().split()))
nums = list(map(int, input().split()))
 
dp = [float('inf') for _ in range(n)]
dp[0] = 0
 
for i in range(1, n):
  for j in range(max(0, i-k), i):
    dp[i] = min(dp[i], dp[j] + abs(nums[i]-nums[j]))
print(dp[-1])
Buggy python submission (verdict: Runtime Error):
n, w = list(map(int, input().split()))
nums = []
for _ in range(n):
  nums.append(list(map(int, input().split())))

dp = [[0 for _ in range(w+1)] for _ in range(1, n)]

for i in range(1, n):
  for j in range(1, w+1):
    if j >= nums[i-1][1]:
      dp[i][j] = max(dp[i][j], dp[i-1][j-nums[i-1][1]] + nums[i-1][0])
    else:
      dp[i][j] = max(dp[i][j], dp[i-1][j])
print(max(dp[-1][-1]))

Fixed submission:
n, w = list(map(int, input().split()))
nums = []
for _ in range(n):
  nums.append(list(map(int, input().split())))
  
dp = [[0 for _ in range(w+1)] for _ in range(n+1)]

for i in range(1, n+1):
  for j in range(1, w+1):
    if j < nums[i-1][0]:
      dp[i][j] = dp[i-1][j]
    else:
      dp[i][j] = max(dp[i-1][j], dp[i-1][j-nums[i-1][0]] + nums[i-1][1])
print(dp[-1][-1])
Buggy python submission (verdict: Runtime Error):
s = input()
t = input()
m, n = len(s), len(t)
dp = [[0 for _ in range(n+1)] for _ in range(m+1)]

for i in range(1, m+1):
  for j in range(1, n+1):
    if s[i-1] == t[j-1]:
      dp[i][j] = d[i-1][j-1] + 1
    else:
      dp[i][j] = max(dp[i-1][j], dp[i][j-1])

res = ''
i, j = m, n
while i > 0 and j > 0:
  if dp[i][j] == dp[i-1][j]:
    i -= 1
  elif dp[i][j] == dp[i][j-1]:
    j -= 1
  else:
    i -= 1
    j -= 1
    res = s[i] + res
print(res)

Fixed submission:
s = input()
t = input()
m, n = len(s), len(t)
dp = [[0 for _ in range(n+1)] for _ in range(m+1)]

for i in range(1, m+1):
  for j in range(1, n+1):
    if s[i-1] == t[j-1]:
      dp[i][j] = dp[i-1][j-1] + 1
    else:
      dp[i][j] = max(dp[i-1][j], dp[i][j-1])

res = ''
i, j = m, n
while i > 0 and j > 0:
  if dp[i][j] == dp[i-1][j]:
    i -= 1
  elif dp[i][j] == dp[i][j-1]:
    j -= 1
  else:
    i -= 1
    j -= 1
    res = s[i] + res
print(res)

Buggy python submission (verdict: Runtime Error):
s = input()
t = input()
m, n = len(s), len(t)
dp = [[0 for _ in range(n+1)] for _ in range(m+1)]

for i in range(1, m+1):
  for j in range(1, n+1):
    if s[i] == t[j]:
      dp[i][j] = d[i-1][j-1] + 1
    else:
      dp[i][j] = max(dp[i-1][j], dp[i][j-1])

res = ''
i, j = m, n
while i > 0 and j > 0:
  if dp[i][j] == dp[i-1][j]:
    i -= 1
  elif dp[i][j] == dp[i][j-1]:
    j -= 1
  else:
    i -= 1
    j -= 1
    res += s[i]
print(res[::-1])

Fixed submission:
s = input()
t = input()
m, n = len(s), len(t)
dp = [[0 for _ in range(n+1)] for _ in range(m+1)]

for i in range(1, m+1):
  for j in range(1, n+1):
    if s[i-1] == t[j-1]:
      dp[i][j] = dp[i-1][j-1] + 1
    else:
      dp[i][j] = max(dp[i-1][j], dp[i][j-1])

res = ''
i, j = m, n
while i > 0 and j > 0:
  if dp[i][j] == dp[i-1][j]:
    i -= 1
  elif dp[i][j] == dp[i][j-1]:
    j -= 1
  else:
    i -= 1
    j -= 1
    res = s[i] + res
print(res)
Buggy python submission (verdict: Runtime Error):
n = int(input())
p = list(map(float, input().split()))

def dfs(cur, n, p, cnt, res, memo):
  if cur == n:
    if cnt > 0:
      return res
    return 0
  if (cur, cnt, res) in memo:
    return memo[(cur, cnt, res)]
  r = dfs(cur+1, n, p, cnt+1, res*p[cur], memo) + dfs(cur+1, n, p, cnt-1, res*(1-p[cur]), memo)
  memo[(cur, cnt, res)] = r
  return memo[(cur, cnt, res)]

print(dfs(0, n, p, 0, 1, {}))

Fixed submission:
n = int(input())
p = list(map(float, input().split()))

dp = [[0 for _ in range(n+1)] for _ in range(n+1)]

dp[0][0] = 1

for i in range(1, n+1):
  dp[i][0] = dp[i-1][0] * (1-p[i-1])
  
for i in range(1, n+1):
  for j in range(1, i+1):
    dp[i][j] = dp[i-1][j] * (1-p[i-1]) + dp[i-1][j-1] * p[i-1]
    
print(sum(dp[-1][(n+1)//2:]))
Buggy python submission (verdict: Runtime Error):
n, k = map(int, input().split())
stones = list(map(int, input.split()))

dp = [False for _ in range(k+1)]

for i in range(k+1):
  for j in stones:
    if i >= j and dp[i-j] == False:
      dp[i] = True
      continue
      
if dp[k]:
  print('First')
else:
  print('Second')

Fixed submission:
n, k = map(int, input().split())
stones = list(map(int, input().split()))

dp = [False for _ in range(k+1)]

for i in range(1, k+1):
  for j in stones:
    if i >= j and dp[i-j] == False:
      dp[i] = True
      continue
      
if dp[k]:
  print("First")
else:
  print("Second")

Buggy python submission (verdict: Runtime Error):
n, k = map(int, input().split())
stones = list(map(int, input.split()))

dp = [False for _ in range(k+1)]

for i in range(1, k+1):
  for j in stones:
    if i >= j and dp[i-j] == False:
      dp[i] = True
      continue
      
if dp[k]:
  print('First')
else:
  print('Second')

Fixed submission:
n, k = map(int, input().split())
stones = list(map(int, input().split()))

dp = [False for _ in range(k+1)]

for i in range(1, k+1):
  for j in stones:
    if i >= j and dp[i-j] == False:
      dp[i] = True
      continue
      
if dp[k]:
  print("First")
else:
  print("Second")
Buggy python submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(10**9)
n , k = [int(i) for i in input().strip().split()]
arr = [int(i) for i in input().strip().split()]
dp = [-1]*(10**5+3)
def cal(i):
    if i>=n-1:
        return 0
 
    elif dp[i]==-1:
        m=10**9
        for j in range(i+1,min(n,i+k+1)):
            m=min(m,cal(j)+abs(arr[j]-arr[i]))
        dp[i]=m
    return dp[i]

Fixed submission:

from functools import lru_cache
import sys
sys.setrecursionlimit(10**9)
n = int(input())
arr = [int(i) for i in input().strip().split()]

@lru_cache(None)
def cal(i):
    if i>=n-1:
        return 0
    else:
        if i==n-2:
            return cal(i+1)+abs(arr[i]-arr[i+1])

        return min(cal(i+1)+abs(arr[i]-arr[i+1]),cal(i+2)+abs(arr[i]-arr[i+2]))

print(cal(0))

Buggy python submission (verdict: Runtime Error):

from functools import lru_cache
n = int(input())
arr = [int(i) for i in input().strip().split()]

@lru_cache(None)
def cal(i):
    if i>=n-1:
        return 0
    else:
        if i==n-2:
            return cal(i+1)+abs(arr[i]-arr[i+1])

        return min(cal(i+1)+abs(arr[i]-arr[i+1]),cal(i+2)+abs(arr[i]-arr[i+2]))

print(cal(0))

Fixed submission:

from functools import lru_cache
import sys
sys.setrecursionlimit(10**9)
n = int(input())
arr = [int(i) for i in input().strip().split()]

@lru_cache(None)
def cal(i):
    if i>=n-1:
        return 0
    else:
        if i==n-2:
            return cal(i+1)+abs(arr[i]-arr[i+1])

        return min(cal(i+1)+abs(arr[i]-arr[i+1]),cal(i+2)+abs(arr[i]-arr[i+2]))

print(cal(0))
Buggy python submission (verdict: Time Limit Exceeded):

from functools import lru_cache
import sys
sys.setrecursionlimit(10**9)
n = int(input())
arr = []
for i in range(n):
    arr.append([int(i) for i in input().split()])

@lru_cache(None)
def cal(i,action):
    if i>=len(arr):
        return 0

    if action==0:
        return max(cal(i+1,1)+arr[i][1],cal(i+1,2)+arr[i][2])

    elif action==1:
        return max(cal(i+1,0)+arr[i][0],cal(i+1,2)+arr[i][2]) 
    
    else:
        return max(cal(i+1,1)+arr[i][1],cal(i+1,0)+arr[i][0])
    

print(max(cal(0,0),cal(0,1),cal(0,2)))

Fixed submission:

import sys
sys.setrecursionlimit(10**9)
n = int(input())
arr = []
for i in range(n):
    arr.append([int(i) for i in input().split()])

dp = [[-1 for i in range(n+2)] for i in range(3)]

def cal(i,action):

    if i>=len(arr):
        return 0

    if dp[action][i]==-1:
        if action==0:
            dp[action][i] = max(cal(i+1,1)+arr[i][1],cal(i+1,2)+arr[i][2])

        elif action==1:
            dp[action][i] = max(cal(i+1,0)+arr[i][0],cal(i+1,2)+arr[i][2]) 
        
        else:
            dp[action][i] = max(cal(i+1,1)+arr[i][1],cal(i+1,0)+arr[i][0])
        
    return dp[action][i]
print(max(cal(0,0),cal(0,1),cal(0,2)))
Buggy python submission (verdict: Time Limit Exceeded):

def asum(l,r):
	global cumsum
	l+=1
	r+=1
	return cumsum[r-1]-cumsum[l-1]
def check(l,r):
	global dp
	if l==r:
		return 0
	if l == r-1:
		return arr[l]+arr[r]
	if dp[l][r] != None:
		return dp[l][r]
	else:
		ans = 10**18
		for i in range(l, r):
			st1 = asum(l,i)
			st2 = asum(i,r+1)
			ans = min(st1 + st2 + check(l,i)+ check(i+1, r), ans)
		
		dp[l][r] = ans
		return ans





ll = int(input())
arr = [int(i) for i in input().split()]
cumsum = [0]

for i in arr:
	cumsum.append(cumsum[-1]+i)
dp = [[None for i in range(ll+1)] for j in range(ll+1)]
print(check(0, ll-1))


Fixed submission:

def asum(l,r):
	global cumsum
	l+=1
	r+=1
	return cumsum[r-1]-cumsum[l-1]
def check(l,r):
	global dp
	if l==r:
		return 0
	if l == r-1:
		return arr[l]+arr[r]
	if dp[l][r] != None:
		return dp[l][r]
	else:
		ans = 10**18
		for i in range(l, r):
			st1 = asum(l,i)
			st2 = asum(i,r+1)
			ans = min(st1 + st2 + check(l,i)+ check(i+1, r), ans)
		
		dp[l][r] = ans
		return ans





ll = int(input())
arr = [int(i) for i in input().split()]
cumsum = [0]

for i in arr:
	cumsum.append(cumsum[-1]+i)
dp = [[None for i in range(ll+1)] for j in range(ll+1)]
print(check(0, ll-1))
Buggy python submission (verdict: Time Limit Exceeded):
def args():
    N, W = tuple(map(int, input().split()))

    Wi, Vi = [], []
    for _ in range(N):
        w, v = tuple(map(int, input().split()))
        Wi.append(w)
        Vi.append(v)

    # print(N, W)
    # print(Wi, Vi)

    return N, W, Wi, Vi


def solve(N, W, Wi, Vi):
    if N == 1:
        return Vi[0]

    x, y = N + 1, max(Vi) * N + 1
    DP = [[float("inf") for _ in range(y)] for _ in range(x)]

    # print(len(DP[0]))

    DP[0][0] = 0

    for i in range(N):
        value = Vi[i]
        w_max = max(Vi) * N
        for v in range(w_max):
            remain = v - value
            if 0 <= remain:
                # 選ぶ
                DP[i + 1][v] = min(DP[i + 1][v], DP[i][remain] + Wi[i])
            # 選ばない
            DP[i + 1][v] = min(DP[i + 1][v], DP[i][v])

    # print(DP)
    ans = 0
    for line in DP:
        for v, e in enumerate(line):
            if not e == float("inf") and e <= W:
                # print(v, e)
                ans = max(ans, v)

    # print(DP)

    return ans


if __name__ == '__main__':
    res = solve(*args())
    print(res)


Fixed submission:
def args():
    N, W = tuple(map(int, input().split()))

    Wi, Vi = [], []
    for _ in range(N):
        w, v = tuple(map(int, input().split()))
        Wi.append(w)
        Vi.append(v)

    # print(N, W)
    # print(Wi, Vi)

    return N, W, Wi, Vi


def solve(N, W, Wi, Vi):
    DP = [[float("inf")] * (sum(Vi) + 1) for _ in range(N + 1)]

    DP[0][0] = 0

    for i in range(N):
        value = Vi[i]
        w_max = sum(Vi) + 1
        for v in range(w_max):
            remain = v - value
            if 0 <= remain:
                # 選ぶ
                DP[i + 1][v] = min(DP[i + 1][v], DP[i][remain] + Wi[i])
            # 選ばない
            DP[i + 1][v] = min(DP[i + 1][v], DP[i][v])

    # print(DP)
    ans = 0
    for line in DP:
        for v, e in enumerate(line):
            if not e == float("inf") and e <= W:
                # print(v, e)
                ans = max(ans, v)

    # print(DP)

    return ans


if __name__ == '__main__':
    res = solve(*args())
    print(res)