Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
import re
s = input()

while s != "":
  if len(s) < 5:
    print('NO')
    exit()
  if s.endswith('dream'):
    s = re.sub("dream$", "", s)
  elif s.endswith('dreamer'):
    s = re.sub("dreamer$", "", s)
  elif s.endswith('erase'):
    s = re.sub("erase$", "", s)
  elif s.endswith('eraser'):
    s = re.sub("eraser$", "", s)
  else:
    print('NO')
    exit()
  
print('YES')

Fixed submission:
import re
s = input()

s = s.replace("eraser", "").replace("erase","")\
	.replace("dreamer", "").replace("dream","")

print('NO' if s else 'YES')
Buggy python submission (verdict: Runtime Error):
from collections import defaultdict


def longest_path(n, edges):
    adj_list = defaultdict(list)
    for x, y in edges:  # x -> y
        adj_list[y].append(x)

    distances = [None] * n

    def dfs(x):
        if distances[x] is None:
            if adj_list[x]:
                for y in adj_list[x]:
                    dfs(y)
                distances[x] = max((distances[y] + 1 for y in adj_list[x]))
            else:
                distances[x] = 0

    for x in range(n):
        dfs(x)

    return max(distances)


def main():
    n, m = [int(x) for x in input().split()]
    edges = [None] * m
    for i in range(m):
        edges[i] = [int(x) - 1 for x in input().split()]

    return longest_path(n, edges)


print(main())


Fixed submission:
from collections import defaultdict, deque


def longest_path(n, edges):
    adj_list = defaultdict(list)
    for x, y in edges:  # x -> y
        adj_list[y].append(x)

    state = [0] * n
    distances = [0] * n
    stack = deque(range(n))

    while stack:
        x = stack.pop()
        if state[x] == 0:
            state[x] = 1
            stack.append(x)
            stack.extend(adj_list[x])
        elif state[x] == 1:
            state[x] = 2
            if adj_list[x]:
                distances[x] = max(distances[y] for y in adj_list[x]) + 1

    return max(distances)


def main():
    n, m = [int(x) for x in input().split()]
    edges = [None] * m
    for i in range(m):
        edges[i] = [int(x) - 1 for x in input().split()]

    return longest_path(n, edges)


print(main())

Buggy python submission (verdict: Runtime Error):
from collections import defaultdict


def longest_path(n, edges):
    adj_list = defaultdict(list)
    for x, y in edges:  # x -> y
        adj_list[y].append(x)

    distances = [None] * n

    def dfs(x):
        if distances[x] is None:
            for y in adj_list[x]:
                dfs(y)
            distances[x] = max((distances[y] + 1 for y in adj_list[x]), default=0)

    for x in range(n):
        dfs(x)

    return max(distances)


def main():
    n, m = [int(x) for x in input().split()]
    edges = [None] * m
    for i in range(m):
        edges[i] = [int(x) - 1 for x in input().split()]

    return longest_path(n, edges)


print(main())


Fixed submission:
from collections import defaultdict, deque


def longest_path(n, edges):
    adj_list = defaultdict(list)
    for x, y in edges:  # x -> y
        adj_list[y].append(x)

    state = [0] * n
    distances = [0] * n
    stack = deque(range(n))

    while stack:
        x = stack.pop()
        if state[x] == 0:
            state[x] = 1
            stack.append(x)
            stack.extend(adj_list[x])
        elif state[x] == 1:
            state[x] = 2
            if adj_list[x]:
                distances[x] = max(distances[y] for y in adj_list[x]) + 1

    return max(distances)


def main():
    n, m = [int(x) for x in input().split()]
    edges = [None] * m
    for i in range(m):
        edges[i] = [int(x) - 1 for x in input().split()]

    return longest_path(n, edges)


print(main())
Buggy python submission (verdict: Runtime Error):
n,k=map(int,input().split())
c=list(map(int,input().split()))
dp=[0]
if n>1:
    dp.append(abs(c[1]-c[0]))
    for i in range(2,n):
        m=10**9+1
        for j in range(1,k+1):
            if j<n:
                m=min(m,dp[max(n-k-1,0)]+abs(c[i]-c[max(0,i-j)]))
        dp.append(m)
print(dp[-1])


Fixed submission:
n=int(input())
c=list(map(int,input().split()))
dp=[0]
if n>1:
    dp.append(abs(c[1]-c[0]))
    for i in range(2,n):
        dp.append(min(dp[-1]+abs(c[i-1]-c[i]),dp[-2]+abs(c[i-2]-c[i])))
print(dp[-1])

Buggy python submission (verdict: Runtime Error):
N=int(input())
L=list(map(int,input().split()))

def mincost(n,cost,dp):
    if not dp.__contains__(n):
        if n==0:
            return 0
        elif n==1:
            dp[n]=abs(cost[1]-cost[0])
            return dp[n]
        else:
            dp[n]=min(abs(cost[n]-cost[n-1])+mincost(n-1,cost,dp),abs(cost[n]-cost[n-2])+mincost(n-2,cost,dp))
            return dp[n]
    else:
        return dp[n]
    
print(mincost(N-1,L,dict()))

Fixed submission:
n=int(input())
c=list(map(int,input().split()))
dp=[0]
if n>1:
    dp.append(abs(c[1]-c[0]))
    for i in range(2,n):
        dp.append(min(dp[-1]+abs(c[i-1]-c[i]),dp[-2]+abs(c[i-2]-c[i])))
print(dp[-1])
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    n,w=map(int,input().split())
    items=[]
    dp=[0 for i in range(w+1)]
    for i in range(n):
        wi,vi=map(int,input().split())
        for j in range(w-wi,-1,-1):
            dp[j+wi]=max(dp[j+wi],dp[j]+vi)
    print(max(dp))
if __name__=='__main__':
    main()


Fixed submission:
n,w=map(int,input().split())
items=[]
dp=[0 for i in range(w+1)]
for i in range(n):
    wi,vi=map(int,input().split())
    for j in range(w-wi,-1,-1):
        dp[j+wi]=max(dp[j+wi],dp[j]+vi)
print(max(dp))
Buggy python submission (verdict: Runtime Error):
n=int(input())
a=[0]*n
b=[0]*n
c=[0]*n
for i in range(n):
    a[i], b[i], c[i] = map(int, input().split() )

z=[[0,0,0] for _ in range(n)]
z[0]=[a[0], b[0], c[0]]
for i in range(1, n):
    z[i][0]=max(a[i]+z[i-1][1], a[i]+z[i-1][2])
    z[i][1]=max(b[i]+z[i-1][0], b[i]+z[i-1][2])
    z[i][2]=max(c[i]+z[i-1][0], c[i]+z[i-1][1])

print(max(z[-1]))


Fixed submission:
n=int(input())
k=2

a=list(map(int, input().split()))

if n<3:
    print(abs(a[0]-a[-1]))
    exit()

c=[0]*n
c[-1]=0
mini=1000000

for i in reversed(range(n-k, n-1)):
    # print(i)
    c[i]=abs(a[i]-a[n-1])
    mini=min(mini, c[i])


for i in reversed(range(n-k)):
    c[i]=min([c[t]+abs(a[i]-a[t]) for t in range(i+1, i+k+1)])

# print("?", c)

print(c[0])
Buggy python submission (verdict: Time Limit Exceeded):
import math
n, k=map(int, input().split() )
a=list(map(int, input().split() ) )
b=[0]*n
for i in range(1, n):
    m=float("inf")
    for j in range(min(i,k),0,-1):
        m=min(m, b[i-j]+int(math.fabs(a[i]-a[i-j])))
    b[i] = m
print(b[-1])

Fixed submission:
n, k=list(map(int, input().split()))
 
a=list(map(int, input().split()))
 
if n<3:
    print(abs(a[0]-a[-1]))
    exit()
 
c=[0]*n
c[-1]=0
mini=1000000
 
for i in reversed(range(n-k, n-1)):
    # print(i)
    c[i]=abs(a[i]-a[n-1])
    mini=min(mini, c[i])
 
 
for i in reversed(range(n-k)):
    c[i]=min([c[t]+abs(a[i]-a[t]) for t in range(i+1, i+k+1)])
 
# print("?", c)
 
print(c[0])

Buggy python submission (verdict: Time Limit Exceeded):
#

n, k=list(map(int, input().split()))

a=list(map(int, input().split()))

if n<3:
    print(abs(a[0]-a[-1]))
    exit()

c=[0]*n
c[-1]=0
mini=1000000

for i in reversed(range(n-k, n-1)):
    # print(i)
    c[i]=abs(a[i]-a[n-1])
    mini=min(mini, c[i])


for i in reversed(range(n-k)):
    c[i]=min([c[t]+abs(a[i]-a[t]) for t in range(i+1, i+k+1)])

# print("?", c)

print(c[0])

Fixed submission:
n, k=list(map(int, input().split()))
 
a=list(map(int, input().split()))
 
if n<3:
    print(abs(a[0]-a[-1]))
    exit()
 
c=[0]*n
c[-1]=0
mini=1000000
 
for i in reversed(range(n-k, n-1)):
    # print(i)
    c[i]=abs(a[i]-a[n-1])
    mini=min(mini, c[i])
 
 
for i in reversed(range(n-k)):
    c[i]=min([c[t]+abs(a[i]-a[t]) for t in range(i+1, i+k+1)])
 
# print("?", c)
 
print(c[0])
Buggy python submission (verdict: Time Limit Exceeded):
import sys
n, m = map(int, input().split())
e=[ set() for _ in range(n+1) ]
c=[0]*(n+1)
s1=set()
s2=set()
for _ in range(m):
    a, b = map(int, sys.stdin.readline().split())
    s1.add(a)
    s2.add(b)
    e[a].add(b) 

s1=s1-s2
# print(s1)
i=0
q=[ list(s1) ]
while q:
    t=[]
    for lst in q:
        for w in lst:
            if e[w]: t.append(e[w])
            c[w]=i
    q=t
    i=i+1

print(i-1) 

Fixed submission:
n, m = map(int, input().split())
dp=[0]*(n+1)
e=[ set() for _ in range(n+1)]
for _ in range(m):
    a, b = map(int, input().split())
    e[a].add(b)
    dp[b]+=1

q=[0]*(n+1)
j=0
for z in range(len(dp)):
    if dp[z]==0:
        q[j]=z
        j=j+1
color=0
i=1
while i<j:
    end=j
    for qel in range(i, end):
        for w in e[q[qel]]:
            dp[w]-=1
            if dp[w]==0: 
                q[j]=w
                j=j+1
    i=end
    color=color+1

print(color-1)

Buggy python submission (verdict: Time Limit Exceeded):
n, m = map(int, input().split())
e=[[] for _ in range(n+1)]
c=[0]*(n+1)
s1=set()
s2=set()
for _ in range(m):
    a, b = map(int, input().split())
    s1.add(a)
    s2.add(b)
    e[a].append(b)

s1=s1-s2

for v in s1:
    i=0
    q=e[v]
    while q:
        i=i+1
        t=[]
        for w in q:
            t.extend(e[w])
            if c[w]<i: c[w]=i
        q=t

print(max(c))

Fixed submission:
n, m = map(int, input().split())
dp=[0]*(n+1)
e=[ set() for _ in range(n+1)]
for _ in range(m):
    a, b = map(int, input().split())
    e[a].add(b)
    dp[b]+=1

q=[0]*(n+1)
j=0
for z in range(len(dp)):
    if dp[z]==0:
        q[j]=z
        j=j+1
color=0
i=1
while i<j:
    end=j
    for qel in range(i, end):
        for w in e[q[qel]]:
            dp[w]-=1
            if dp[w]==0: 
                q[j]=w
                j=j+1
    i=end
    color=color+1

print(color-1)

Buggy python submission (verdict: Time Limit Exceeded):
n, m = map(int, input().split())
e=[[] for _ in range(n+1)]
c=[0]*(n+1)
s1=set()
s2=set()
for _ in range(m):
    a, b = map(int, input().split())
    s1.add(a)
    s2.add(b)
    e[a].append(b)

s1=s1-s2

for v in s1:
    i=0
    q=e[v]
    while q:
        i=i+1
        t=[]
        for w in q:
            t.extend(e[w])
            if c[w]<i: c[w]=i
        q=t

print(max(c))

Fixed submission:
n, m = map(int, input().split())
dp=[0]*(n+1)
e=[ set() for _ in range(n+1)]
for _ in range(m):
    a, b = map(int, input().split())
    e[a].add(b)
    dp[b]+=1

q=[0]*(n+1)
j=0
for z in range(len(dp)):
    if dp[z]==0:
        q[j]=z
        j=j+1
color=0
i=1
while i<j:
    end=j
    for qel in range(i, end):
        for w in e[q[qel]]:
            dp[w]-=1
            if dp[w]==0: 
                q[j]=w
                j=j+1
    i=end
    color=color+1

print(color-1)
Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
p=list( float(s) for s in input().split() )
res=[1-p[0], p[0]]+[0]*(n//2 - 1)
for i in range(1,n):
    res[len(res)-1]=(1-p[i])*res[len(res)-1]
    for j in range(len(res)-2, -1, -1):
        res[j+1]+=(res[j]*p[i])
        res[j]=(res[j]*(1-p[i]))        
print( (1-sum(res[:1+n//2])) )

Fixed submission:
n=int(input())
p=list( float(s) for s in input().split() )
 
res=[1-p[0], p[0]]+[0]*(n//2 - 1)
for i in range(1,n):
    for j in range(len(res)-1, 0, -1):
        res[j]=(res[j]*(1-p[i]) + (res[j-1]*p[i]) )
    res[0]=res[0]*(1-p[i])
print( (1-sum(res[:1+n//2])) )

Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
p=list( int(s[2:]) for s in input().split() )
z=0
res=[100-p[0], p[0]]+[0]*(n//2 - 1)
for i in range(1,n):
    z=z+1
    for j in range(len(res)-1, 0, -1):
        res[j]=(res[j]*(100-p[i]) + (res[j-1]*p[i]) )
    res[0]=res[0]*(100-p[i])
    if z==10:
        for x in res: x=x//100**5
        z=5
print( 1-(sum(res[:1+n//2])/(100**(z+1)) ) )

Fixed submission:
n=int(input())
p=list( float(s) for s in input().split() )
 
res=[1-p[0], p[0]]+[0]*(n//2 - 1)
for i in range(1,n):
    for j in range(len(res)-1, 0, -1):
        res[j]=(res[j]*(1-p[i]) + (res[j-1]*p[i]) )
    res[0]=res[0]*(1-p[i])
print( (1-sum(res[:1+n//2])) )

Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
p=list( int(s[2:]) for s in input().split() )
z=0
res=[100-p[0], p[0]]+[0]*(n//2 - 1)
for i in range(1,n):
    z=z+1
    for j in range(len(res)-1, 0, -1):
        res[j]=(res[j]*(100-p[i]) + (res[j-1]*p[i]) )
    res[0]=res[0]*(100-p[i])
    if z==10:
        for x in res: x=x//100**5
        z=5
print( 1-(sum(res[:1+n//2])/(100**(z+1)) ) )

Fixed submission:
n=int(input())
p=list( float(s) for s in input().split() )
 
res=[1-p[0], p[0]]+[0]*(n//2 - 1)
for i in range(1,n):
    for j in range(len(res)-1, 0, -1):
        res[j]=(res[j]*(1-p[i]) + (res[j-1]*p[i]) )
    res[0]=res[0]*(1-p[i])
print( (1-sum(res[:1+n//2])) )

Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
p=list( float(s) for s in input().split() )

res=[1-p[0], p[0]]+[0]*(n//2 - 1)
for i in range(1,n):
    for j in range(len(res)-1, 0, -1):
        res[j]=(res[j]*(1-p[i]) + (res[j-1]*p[i]) )
    res[0]=res[0]*(1-p[i])
print( (1-sum(res[:1+n//2])) )

Fixed submission:
n=int(input())
p=list( float(s) for s in input().split() )
 
res=[1-p[0], p[0]]+[0]*(n//2 - 1)
for i in range(1,n):
    for j in range(len(res)-1, 0, -1):
        res[j]=(res[j]*(1-p[i]) + (res[j-1]*p[i]) )
    res[0]=res[0]*(1-p[i])
print( (1-sum(res[:1+n//2])) )
Buggy python submission (verdict: Runtime Error):
from functools import lru_cache
import sys

sys.setrecursionlimit(10**5)

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

@lru_cache(maxsize=None)
def recur(i):
    if i == N - 1:
        return 0
    return min(abs(h[i] - h[i + 1]) + recur(i + 1), abs(h[i] - h[min(N - 1, i + 2)]) + recur(min(N - 1, i + 2)))

print(recur(0))

# dp = [0]*(N + 1)
# for i in range(N):


Fixed submission:
from functools import lru_cache
import sys

sys.setrecursionlimit(10**6)

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

@lru_cache(maxsize=None)
def recur(i):
    if i == N - 1:
        return 0
    return min(abs(h[i] - h[i + 1]) + recur(i + 1), abs(h[i] - h[min(N - 1, i + 2)]) + recur(min(N - 1, i + 2)))

print(recur(0))

# dp = [0]*(N + 1)
# for i in range(N):

Buggy python submission (verdict: Runtime Error):
from functools import lru_cache

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

@lru_cache(maxsize=None)
def recur(i):
    if i == N - 1:
        return 0
    return min(abs(h[i] - h[i + 1]) + recur(i + 1), abs(h[i] - h[min(N - 1, i + 2)]) + recur(min(N - 1, i + 2)))

print(recur(0))

# dp = [0]*(N + 1)
# for i in range(N):


Fixed submission:
from functools import lru_cache
import sys

sys.setrecursionlimit(10**6)

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

@lru_cache(maxsize=None)
def recur(i):
    if i == N - 1:
        return 0
    return min(abs(h[i] - h[i + 1]) + recur(i + 1), abs(h[i] - h[min(N - 1, i + 2)]) + recur(min(N - 1, i + 2)))

print(recur(0))

# dp = [0]*(N + 1)
# for i in range(N):
Buggy python submission (verdict: Time Limit Exceeded):
N, K = map(int, input().split())
h = list(map(int, input().split()))

dp = [float("inf")]*(N + 2)
dp[0] = 0
for i in range(N):
    for k in range(1, K + 1):
        if i < N - k:
            dp[i + k] = min(dp[i + k], abs(h[i] - h[i + k]) + dp[i])

print(dp[N - 1])


Fixed submission:
N, K = map(int, input().split())
h = list(map(int, input().split()))

dp = [float("inf")]*(N + 2)
dp[0] = 0
for i in range(N):
    for k in range(1, min(K + 1, N - i)):
        dp[i + k] = min(dp[i + k], abs(h[i] - h[i + k]) + dp[i])

print(dp[N - 1])
Buggy python submission (verdict: Runtime Error):
## tasks https://atcoder.jp/contests/dp/tasks
## TODO

def solution():
    # result array for calculation for optimal cost for every stone
    res = [[-1 for x in range(3)] for y in range(n)]
    res[0] = a[0]
    for i in range(1,n):
        # going through the all days
        for j in range(3):
            # calucaltion for every possible actions, but skipping the same activity
            # picked current activity is j, let us get options from non j and get max of them
            # it will be a cost for j
            # do it for every

            #searching for best previous happines
            bph = -1
            for o in range(3):
                #skipping the same activity
                if o==j:
                    continue
                bph = max(bph, res[i-1][o])
            #print("res = {} a = {}".format(res, a))
            #print("i={} j={}".format(i, j))
            res[i][j] = max(res[i][j], bph + a[i][j])

    return max(res[-1][0],res[-1][1],res[-1][2])


if __name__ == "__main__":
    n = int(input())

    a = [[None for x in range(3)] for y in range(n)]

    for i in range(n):
        row = list(map(int, raw_input().split(" ")))
        for j in range(3):
            a[i][j] = row[j]

    #print("n = {} a = {}".format(n, a))
    if n == 1:
        print max(a[0][0],a[0][1],a[0][2])
    else:
        print(solution())


Fixed submission:
## tasks https://atcoder.jp/contests/dp/tasks
## TODO

def solution():
    # result array for calculation for optimal cost for every stone
    res = [[-1 for x in range(3)] for y in range(n)]
    res[0] = a[0]
    for i in range(1,n):
        # going through the all days
        for j in range(3):
            # calucaltion for every possible actions, but skipping the same activity
            # picked current activity is j, let us get options from non j and get max of them
            # it will be a cost for j
            # do it for every

            #searching for best previous happines
            bph = -1
            for o in range(3):
                #skipping the same activity
                if o==j:
                    continue
                bph = max(bph, res[i-1][o])
            #print("res = {} a = {}".format(res, a))
            #print("i={} j={}".format(i, j))
            res[i][j] = max(res[i][j], bph + a[i][j])

    return max(res[-1][0],res[-1][1],res[-1][2])


if __name__ == "__main__":
    n = int(input())

    a = [[None for x in range(3)] for y in range(n)]

    for i in range(n):
        row = list(map(int, input().split(" ")))
        for j in range(3):
            a[i][j] = row[j]

    #print("n = {} a = {}".format(n, a))
    if n == 1:
        print(max(a[0][0],a[0][1],a[0][2]))
    else:
        print(solution())
Buggy python submission (verdict: Runtime Error):
n, k = [int(x) for x in input().split()]
arr = [int(x) for x in input().split()]
dp = [float('inf') for x in arr]
dp[0] = 0
for i in range(1, n):
  dp[i] = min(dp[j] + abs(arr[i] - arr[j]) for j in range(max(i-k, 0), i))
print(dp[-1])

Fixed submission:
n = int(input())
arr = [int(x) for x in input().split()]
dp = [float('inf') for x in arr]
dp[0] = 0
for i in range(n):
    for j in (i+1, i+2):
        if j < n:
            dp[j] = min(dp[j], dp[i] + abs(arr[i] - arr[j]))
print(dp[-1])

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

Fixed submission:
n = int(input())
arr = [int(x) for x in input().split()]
dp = [float('inf') for x in arr]
dp[0] = 0
for i in range(n):
    for j in (i+1, i+2):
        if j < n:
            dp[j] = min(dp[j], dp[i] + abs(arr[i] - arr[j]))
print(dp[-1])

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

Fixed submission:
n = int(input())
arr = [int(x) for x in input().split()]
dp = [float('inf') for x in arr]
dp[0] = 0
for i in range(n):
    for j in (i+1, i+2):
        if j < n:
            dp[j] = min(dp[j], dp[i] + abs(arr[i] - arr[j]))
print(dp[-1])
Buggy python submission (verdict: Time Limit Exceeded):
INF = float('infinity')

N, K = map(int, input().split())
H = [int(c) for c in input().split()]

dp = [INF] * N
dp[0] = 0

for i in range(1, N):
    for k in range(1, K+1):
        if i - k >= 0:
            dp[i] = min(dp[i], dp[i-k] + abs(H[i] - H[i-k]))

print(dp[N-1])

Fixed submission:
INF = float('infinity')

N, K = map(int, input().split())
H = [int(c) for c in input().split()]

dp = [INF] * N
dp[0] = 0

for i in range(1, N):
    for k in range(1, K+1):
        if i - k >= 0:
            dp[i] = min(dp[i], dp[i-k] + abs(H[i] - H[i-k]))

print(dp[N-1])
Buggy python submission (verdict: Runtime Error):
#include <bits/stdc++.h>
using namespace std;

int main() {
    int N, W;
    cin >> N >> W;

    vector<int> dp = vector<int>(W + 1, 0);
    vector<int> idx = vector<int>(1, 0);
    int ans = 0;

    for (int i = 0; i < N; i++) {
        int w, v;
        cin >> w >> v;
        vector<int> new_idx = vector<int>(1, 0);
        for (const auto& k : idx) {
            if (k + w <= W) {
                dp[k + w] = max(dp[k + w], dp[k] + v);
                new_idx.push_back(k + w);
                ans = max(ans, dp[k + w]);
            }
        }
        idx.insert(idx.end(), new_idx.begin(), new_idx.end());
    }

    cout << ans << endl;
}

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

dp = [0] * (W + 1)
weights2check = [0]
ans = 0
for _ in range(N):
    w, v = map(int, input().split())
    for k in range(W-w, -1, -1):
        dp[k + w] = max(dp[k + w], dp[k] + v)
        ans = max(ans, dp[k + w])


print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
N, W = map(int, input().split())

dp = [0] * (W + 1)
weights2check = [0]
for _ in range(N):
    w, v = map(int, input().split())
    new_weights2check = []
    for k in weights2check:
        if k + w <= W:
            dp[k + w] = max(dp[k + w], dp[k] + v)
            new_weights2check.append(k + w)

    weights2check += new_weights2check


ans = max(dp[i] for i in weights2check)
print(ans)

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

dp = [0] * (W + 1)
weights2check = [0]
ans = 0
for _ in range(N):
    w, v = map(int, input().split())
    for k in range(W-w, -1, -1):
        dp[k + w] = max(dp[k + w], dp[k] + v)
        ans = max(ans, dp[k + w])


print(ans)
Buggy python submission (verdict: Runtime Error):
def main():
    MOD = int(1e9 + 7)
    h, w = map(int, input().split())
    grid = [input() for _ in range(h)]

    dp = [[0] * w for _ in range(h)]
    dp[i][j] = 1

    for i in range(h):
        for j in range(w):
            if grid[i][j] != '#':
                if i > 0:
                    dp[i][j] += dp[i-1][j]

                if j > 0:
                    dp[i][j] += dp[i][j-1]

                if dp[i][j] > MOD:
                    dp[i][j] -= MOD

    ans = dp[h-1][w-1]
    print(ans)



if __name__ == "__main__":
    main()

Fixed submission:
def main():
    MOD = int(1e9 + 7)
    h, w = map(int, input().split())
    grid = [input() for _ in range(h)]

    dp = [[0] * w for _ in range(h)]

    for i in range(h):
        for j in range(w):
            if grid[i][j] != '#':
                if i == 0 and j == 0:
                    dp[i][j] = 1
                
                if i > 0:
                    dp[i][j] += dp[i-1][j]

                if j > 0:
                    dp[i][j] += dp[i][j-1]

                if dp[i][j] > MOD:
                    dp[i][j] -= MOD

    ans = dp[h-1][w-1]
    print(ans)



if __name__ == "__main__":
    main()
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
a = [int(c) for c in input().split()]

dp = [[-1] * N for _ in range(N)]
for i in range(N):
    for L in range(N):
        for R in range(L, N):
            if L == R:
                dp[L][R] = a[L]
            else:
                dp[L][R] = max(a[L] - dp[L+1][R], a[R] - dp[L][R-1])


print(dp[0][N-1])


Fixed submission:
N = int(input())
a = [int(c) for c in input().split()]

dp = [[-1] * N for _ in range(N)]
for L in range(N, -1, -1):
    for R in range(L, N):
        if L == R:
            dp[L][R] = a[L]
        else:
            dp[L][R] = max(a[L] - dp[L+1][R], a[R] - dp[L][R-1])


print(dp[0][N-1])