Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
n,k = map(int,input().split())
arr = [int(i) for i in input().split()]
dp = [0 for j in range(n)]
for i in range(1,n):
    dp[i] = float("inf")
    for j in range(i-1,-1,-1):
        if i-j <= k:
            val = (abs(arr[i]-arr[j]) + dp[j]) 
            dp[i] = min(dp[i],val)
print(dp[n-1])


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

Buggy python submission (verdict: Time Limit Exceeded):
n,k = map(int,input().split())
arr = [int(i) for i in input().split()]
dp = [0 for j in range(n)]
for i in range(1,n):
    dp[i] = float("inf")
    for j in range(i-1,-1,-1):
        if i-j <= k:
            val = (abs(arr[i]-arr[j]) + dp[j]) 
            dp[i] = min(dp[i],val)
print(dp[n-1])


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

Buggy python submission (verdict: Time Limit Exceeded):
n,k = map(int,input().split())
arr = [int(i) for i in input().split()]
dp = [0 for j in range(n)]
for i in range(1,n):
    dp[i] = float("inf")
    for j in range(1,k+1):
        if i-j >=0:
            val = (abs(arr[i]-arr[i-j]) + dp[i-j]) 
            dp[i] = min(dp[i],val)
print(dp[n-1])


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

Buggy python submission (verdict: Time Limit Exceeded):
n,k = map(int,input().split())
arr = [int(i) for i in input().split()]
dp = [0 for j in range(n)]
for i in range(1,n):
    mins = float("inf")
    for j in range(1,k+1):
        val = (abs(arr[i]-arr[i-j]) + dp[i-j]) if i-j >=0  else float("inf")
        mins = min(mins,val)
    dp[i] = mins
print(dp[n-1])


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

Buggy python submission (verdict: Runtime Error):
def getMinCost(arr,i,k):
    if i <= 0: return 0
    mins = float("inf")
    for j in range(1,k+1):
        if j <= i:
            mins = min(mins,abs(arr[i]-arr[i-j]) + getMinCost(arr,i-j,k))
    return mins

n,k = map(int,input().split())
arr = [int(i) for i in input().split()]
print(getMinCost(arr,len(arr)-1,k))


Fixed submission:
n,k = map(int,input().split())
arr = [int(i) for i in input().split()]
dp = [float("inf")] * n
dp[0] = 0
for i in range(n):
    for j in range(i+1,i+k+1):
        if j < n:
            dp[j] = min(dp[j],abs(arr[i]-arr[j]) + dp[i])
print(dp[n-1])
Buggy python submission (verdict: Time Limit Exceeded):
def knapsack(weight,value,N,W,i,cache):
    if i == N or W <= 0:
        return 0
    if cache[i][W] != 0:
        return cache[i][W]
    op1,op2 = 0,0
    if weight[i] <= W:
        op1 = value[i] + knapsack(weight,value,N,W-weight[i],i+1,cache)
    op2 = knapsack(weight,value,N,W,i+1,cache)
    cache[i][W] = max(op1,op2)
    return cache[i][W]

N,W = map(int,input().split())
weight = []
value = []
for i in range(N):
    w,v = map(int,input().split())
    weight.append(w)
    value.append(v)
cache = [[0 for i in range(W+1)] for j in range(N+1)]
print(knapsack(weight,value,N,W,0,cache))

Fixed submission:
N,W = map(int,input().split())
weight = []
value = []
for i in range(N):
    w,v = map(int,input().split())
    weight.append(w)
    value.append(v)
dp = [[0 for i in range(W+1)] for j in range(N+1)]
for i in range(1,N+1):
    for j in range(1,W+1):
        op1,op2 = 0,0
        if weight[i-1] <= j:
            op1 = value[i-1] + dp[i-1][j-weight[i-1]]
        op2 = dp[i-1][j]
        dp[i][j] = max(op1,op2)
print(dp[N][W])
Buggy python submission (verdict: Time Limit Exceeded):
S = input()
T = input()
# S = "abracadabra"
# T = "avadakedavra"
dp = [[[] for i in range(len(T)+1)] for j in range(len(S)+1)]
for i in range(1,len(S)+1):
    for j in range(1,len(T)+1):
        if i == 0 or j == 0: continue
        if S[i-1] == T[j-1]:
            dp[i][j].append("".join(dp[i-1][j-1]) + S[i-1])
        else:
            if len("".join(dp[i-1][j])) >= len("".join(dp[i][j-1])): 
                dp[i][j].append("".join(dp[i-1][j]))
            else:
                dp[i][j].append("".join(dp[i][j-1]))

print("".join(dp[len(S)][len(T)]))

Fixed submission:
S = input()
T = input()
dp = [[0 for i in range(len(T)+1)] for j in range(len(S)+1)]
for i in range(1,len(S)+1):
    for j in range(1,len(T)+1):
        if S[i-1] == T[j-1]:
            dp[i][j] = 1 + dp[i-1][j-1]
        else:
            dp[i][j] = max(dp[i-1][j],dp[i][j-1]) 

length = dp[len(S)][len(T)]
LCS = [0]*length
i = len(S)
j = len(T)
while i > 0 and j > 0: 
    if S[i-1] == T[j-1]: 
        LCS[length-1] = S[i-1]
        i-=1
        j-=1
        length-=1
    elif dp[i-1][j] > dp[i][j-1]: 
        i-=1
    else: 
        j-=1
print("".join(LCS))

Buggy python submission (verdict: Time Limit Exceeded):
S = input()
T = input()
dp = [["" for i in range(len(T)+1)] for j in range(len(S)+1)]
for i in range(1,len(S)+1):
    for j in range(1,len(T)+1):
        if i == 0 or j == 0: continue
        if S[i-1] == T[j-1]:
            dp[i][j] = dp[i-1][j-1] + S[i-1]
        else:
            if len(dp[i-1][j]) >= len(dp[i][j-1]): 
                dp[i][j] = dp[i-1][j]
            else:
                dp[i][j] = dp[i][j-1]
print(dp[len(S)][len(T)])

Fixed submission:
S = input()
T = input()
dp = [[0 for i in range(len(T)+1)] for j in range(len(S)+1)]
for i in range(1,len(S)+1):
    for j in range(1,len(T)+1):
        if S[i-1] == T[j-1]:
            dp[i][j] = 1 + dp[i-1][j-1]
        else:
            dp[i][j] = max(dp[i-1][j],dp[i][j-1]) 

length = dp[len(S)][len(T)]
LCS = [0]*length
i = len(S)
j = len(T)
while i > 0 and j > 0: 
    if S[i-1] == T[j-1]: 
        LCS[length-1] = S[i-1]
        i-=1
        j-=1
        length-=1
    elif dp[i-1][j] > dp[i][j-1]: 
        i-=1
    else: 
        j-=1
print("".join(LCS))
Buggy python submission (verdict: Runtime Error):
from collections import Counter
n = int(input().strip())
a = list(map(int, input().strip().split()))
cnt1 = Counter(a[::2]).most_common(2)
c11, c12 = (cnt1 if len(cnt1) == 2 else cnt1+[('', 0)])
cnt2 = Counter(a[1::2]).most_common(2)
c21, c22 = (cnt2 if len(cnt2) == 2 else cnt2+[('', 0)])

if c11[0] != c21[0]:
    print(n - c11[1] - c21[1])
else:
    print(n - max(c11[1]+c22[1], c12[1]+c21[1]))

Fixed submission:
s = input()
for c in s:
  if c == '1': print('9', end='')
  elif c == '9': print('1', end='')

print()

Buggy python submission (verdict: Runtime Error):
from collections import Counter
n = int(input().strip())
a = list(map(int, input().strip().split()))

c1 = Counter(a[::2])
c2 = Counter(a[1::2])
c1f1 = max(c1, key = lambda k:c1[k])
c2f1 = max(c2, key = lambda k:c2[k])

if c1f1 != c2f1:
  return n - c1[c1f1] - c2[c2f1]
else:
  if c1[c1f1] > c2[c2f1]:
    del c2[c2f1]
    if not c2: return n-c1[c1f1]
    c2f1 = max(c2, key = lambda k:c2[k])
    return n-c1[c1f1] - c2[c2f1]
  else:
    del c1[c1f1]
    if not c1: return n-c2[c2f1]
    c1f1 = max(c1, key = lambda k:c1[k])
    return n-c1[c1f1] - c2[c2f1]

Fixed submission:
s = input()
for c in s:
  if c == '1': print('9', end='')
  elif c == '9': print('1', end='')

print()
Buggy python submission (verdict: Runtime Error):
from collections import Counter
n = int(input().strip())
a = list(map(int, input().strip().split()))
cnt1 = Counter(a[::2]).most_common(2)
c11, c12 = (cnt1 if len(cnt1) == 2 else cnt1+[('', 0)])
cnt2 = Counter(a[1::2]).most_common(2)
c21, c22 = (cnt2 if len(cnt2) == 2 else cnt2+[('', 0)])

if c11[0] != c21[0]:
    print(n - c11[1] - c21[1])
else:
    print(n - max(c11[1]+c22[1], c12[1]+c21[1]))

Fixed submission:
from collections import Counter
n = int(input().strip())
a = list(map(int, input().strip().split()))
cnt1 = Counter(a[::2]).most_common(2)
c11, c12 = (cnt1 if len(cnt1) == 2 else cnt1+[('', 0)])
cnt2 = Counter(a[1::2]).most_common(2)
c21, c22 = (cnt2 if len(cnt2) == 2 else cnt2+[('', 0)])

if c11[0] != c21[0]:
    print(n - c11[1] - c21[1])
else:
    print(n - max(c11[1]+c22[1], c12[1]+c21[1]))

Buggy python submission (verdict: Runtime Error):
from collections import Counter
n = int(input().strip())
a = list(map(int, input().strip().split()))
 
c1 = Counter(a[::2])
c2 = Counter(a[1::2])
c1f1 = max(c1, key = lambda k:c1[k])
c2f1 = max(c2, key = lambda k:c2[k])
 
if c1f1 != c2f1:
  return n - c1[c1f1] - c2[c2f1]
else:
  if c1[c1f1] > c2[c2f1]:
    del c2[c2f1]
    if not c2: return n-c1[c1f1]
    c2f1 = max(c2, key = lambda k:c2[k])
    return n-c1[c1f1] - c2[c2f1]
  else:
    del c1[c1f1]
    if not c1: return n-c2[c2f1]
    c1f1 = max(c1, key = lambda k:c1[k])
    return n-c1[c1f1] - c2[c2f1]

Fixed submission:
from collections import Counter
n = int(input().strip())
a = list(map(int, input().strip().split()))
cnt1 = Counter(a[::2]).most_common(2)
c11, c12 = (cnt1 if len(cnt1) == 2 else cnt1+[('', 0)])
cnt2 = Counter(a[1::2]).most_common(2)
c21, c22 = (cnt2 if len(cnt2) == 2 else cnt2+[('', 0)])

if c11[0] != c21[0]:
    print(n - c11[1] - c21[1])
else:
    print(n - max(c11[1]+c22[1], c12[1]+c21[1]))
Buggy python submission (verdict: Time Limit Exceeded):
from sys import maxint

N, K = map(int,raw_input().split())
stones = map(int,raw_input().split())

costs = [maxint] * N 
costs[0] = 0
for n in range(N) :
  for k in range(1,min(K, N-n-1)+1) : 
    costs[n+k] = min(costs[n+k], costs[n] + abs(stones[n]-stones[n+k]))
  
print costs[-1]

Fixed submission:
from sys import maxint

N, K = map(int,raw_input().split())
stones = map(int,raw_input().split())

costs = [maxint] * N 
costs[0] = 0
for n in range(N) :
  for k in range(1,min(K, N-n-1)+1) : 
    costs[n+k] = min(costs[n+k], costs[n] + abs(stones[n]-stones[n+k]))
  
print costs[-1]
Buggy python submission (verdict: Time Limit Exceeded):
N, M = map(int,raw_input().split())
gra = [set() for n in range(N)]

start = set(range(N))
for m in range(M) :
  x, y = map(int,raw_input().split())
  gra[x-1].add(y-1)
  start.discard(y-1)

mem = [None for n in range(N)]
q = list(start)
for i in q : mem[i] = 0

longest = 0
while q :
  cur = q.pop()
  for nxt in gra[cur] :
    mem[nxt] = mem[cur] + 1
    longest = max(longest, mem[nxt])
    q.append(nxt)

print longest

Fixed submission:
N, M = map(int,raw_input().split())
gra = [set() for n in range(N)]
ins = [0] * N

start = set(range(N))
for m in range(M) :
  x, y = map(int,raw_input().split())
  gra[x-1].add(y-1)
  ins[y-1] += 1
  start.discard(y-1)

mem = [None for n in range(N)]
q = list(start)
for i in q : mem[i] = 0

longest = 0
while q :
  cur = q.pop(0)
  for nxt in gra[cur] :
    ins[nxt] -= 1
    if ins[nxt] == 0 :
      mem[nxt] = mem[cur] + 1
      longest = max(longest, mem[nxt])
      q.append(nxt)

print longest

Buggy python submission (verdict: Runtime Error):
N, M = map(int,raw_input().split())
gra = [set() for n in range(N)]

start = set(range(N))
for m in range(M) :
  x, y = map(int,raw_input().split())
  gra[x-1].add(y-1)
  start.discard(y-1)

def dfs(cur, par=-1) : 
  
  d = [0]
  for nxt in gra[cur] :
    if nxt == par : continue
    d.append(dfs(nxt, cur))

  return max(d) + int(par!=-1)

res = []
while start :
  res.append(dfs(start.pop()))

print max(res)

Fixed submission:
N, M = map(int,raw_input().split())
gra = [set() for n in range(N)]
ins = [0] * N

start = set(range(N))
for m in range(M) :
  x, y = map(int,raw_input().split())
  gra[x-1].add(y-1)
  ins[y-1] += 1
  start.discard(y-1)

mem = [None for n in range(N)]
q = list(start)
for i in q : mem[i] = 0

longest = 0
while q :
  cur = q.pop(0)
  for nxt in gra[cur] :
    ins[nxt] -= 1
    if ins[nxt] == 0 :
      mem[nxt] = mem[cur] + 1
      longest = max(longest, mem[nxt])
      q.append(nxt)

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

Fixed submission:
n = int(input())
heights = list(map(int, input().split()))
dp = [float('inf') for i in range(n)]
dp[0] = 0

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

print(dp[n - 1])

Buggy python submission (verdict: Runtime Error):
n, K = map(int, input().split())
heights = list(map(int, input().split()))
dp = [float('inf') for i in range(n)]
dp[0] = 0

for i in range(1, n):

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

print(dp[n - 1])

Fixed submission:
n = int(input())
heights = list(map(int, input().split()))
dp = [float('inf') for i in range(n)]
dp[0] = 0

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

print(dp[n - 1])
Buggy python submission (verdict: Time Limit Exceeded):
N, W = map(int, input().split())

dp = [[0 for _ in range(W)] for _ in range(N + 1)]
weight = []
value = []
for _ in range(N):
    w, v = map(int, input().split())
    weight.append(w)
    value.append(v)

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

for i in range(W + 1):
    dp[0][i] = 0

for i in range(N):
    for w in range(W + 1):
        if weight[i] <= w:
            dp[i + 1][w] = max(dp[i][w - weight[i]] + value[i], dp[i][w])
        else:
            dp[i + 1][w] = dp[i][w]

print(dp[N][W])


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

dp = [[0 for _ in range(W)] for _ in range(N + 1)]
weight = []
value = []
for _ in range(N):
    w, v = map(int, input().split())
    weight.append(w)
    value.append(v)

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

for i in range(W + 1):
    dp[0][i] = 0

for i in range(N):
    for w in range(W + 1):
        if weight[i] <= w:
            dp[i + 1][w] = max(dp[i][w - weight[i]] + value[i], dp[i][w])
        else:
            dp[i + 1][w] = dp[i][w]

print(dp[N][W])
Buggy python submission (verdict: Runtime Error):
import sys


def input():
    return sys.stdin.readline().strip()


def main():
    size = int(input())
    array = []
    dp = [0] * size
    for _ in range(size):
        z = (list(map(int, input().split())))
        newDp = [0] * size
        for i in range(3):
            for j in range(3):
                if j != i:
                    newDp[j] = max(newDp[j], dp[i] + z[j])
        dp = newDp
    print(max(dp[0],dp[1],dp[2]))


if __name__ == "__main__":
    main()


Fixed submission:
import sys


def input():
    return sys.stdin.readline().strip()


def main():
    size = int(input())
    dp = [0] * 3
    for _ in range(size):
        z = (list(map(int, input().split())))
        newDp = [0] * 3
        for i in range(3):
            for j in range(3):
                if j != i:
                    # import pdb
                    # pdb.set_trace()
                    newDp[j] = max(newDp[j], dp[i] + z[j])
        dp = newDp
    print(max(dp[0],dp[1],dp[2]))


if __name__ == "__main__":
    main()
Buggy python submission (verdict: Time Limit Exceeded):
import sys


def input():
    return sys.stdin.readline().strip()

def main():

    # i have too make index as weight and value as value
    size, total_weight = map(int, input().split())
    dp = [0] * (total_weight+1)
    for _ in range(size):
        weight, val = map(int, input().split())
        for i in range(total_weight - weight, -1, -1):
            dp[weight + i] = max(dp[weight + i], dp[i] + val)
    ans = 0
    for i in range(total_weight+1):
        ans = max(ans, dp[i])
    print(ans)

if __name__ == "__main__":
    main()


Fixed submission:
import sys


def input():
    return sys.stdin.readline().strip()

def main():

    # i have too make index as weight and value as value
    import numpy as np
    N, W = map(int, input().split())

    dp = np.zeros(W + 1, int)

    for i in range(N):
        w, v = map(int, input().split())
        np.maximum(dp[:-w] + v, dp[w:], out=dp[w:])
        # print(dp[:-w],dp[w:] )


    print(dp[-1])


if __name__ == "__main__":
    main()
Buggy python submission (verdict: Runtime Error):
import sys


def input():
    return sys.stdin.readline().strip()

def main():

    # i have too make index as weight and value as value
    import numpy as np
    N, W = map(int, input().split())

    dp = np.zeros(W + 1, int)

    for i in range(N):
        w, v = map(int, input().split())
        np.maximum(dp[:-w] + v, dp[w:], out=dp[w:])
        # print(dp[:-w],dp[w:] )


    print(dp[-1])


if __name__ == "__main__":
    main()


Fixed submission:
import sys


def input():
    return sys.stdin.readline().strip()

def main():

    # i have too make index as weight and value as value
    import numpy as np

    n, capacity = map(int, input().split())
    value_max = 10 ** 5
    dp = np.full(value_max + 1, capacity + 1)
    dp[0] = 0

    for i in range(n):
        w, v = map(int, input().split())
        np.minimum(dp[v:], dp[:-v] + w, out=dp[v:])

    print(np.where(dp <= capacity)[0][-1])


if __name__ == "__main__":
    main()
Buggy python submission (verdict: Runtime Error):
n = int(input())
a = []
d = []
for _ in range(n):
    a.append(list(map(int,input().split())))
    d.append([0,0,0])
d[0]=a[0]
for i in range(1,n):
    for j in range(3):
        d[i][j]=max(d[i-1][(j+1)%3],d[i-1][(j+2)%3])+a[i][j]
print(max(d[n-1]))


Fixed submission:
n = int(input())
a = list(map(int,input().split()))
b = [0]*n
b[1] = abs(a[1]-a[0])
for i in range(2,n):
    b[i]=min(b[i-2]+abs(a[i-2]-a[i]), b[i-1]+abs(a[i-1]-a[i]))
print(b[n-1])
Buggy python submission (verdict: Runtime Error):
n = int(input())
a = list(map(int,input().split()))
b = [0]*n
b[1] = abs(a[1]-a[0])
for i in range(2,n):
    b[i]=min(b[i-2]+abs(a[i-2]-a[i]), b[i-1]+abs(a[i-1]-a[i]))
print(b[n-1])

Fixed submission:
n,k = map(int,input().split())
a = list(map(int,input().split()))
c = [10**9]*n
c[0]=0
c[1]=abs(a[0]-a[1])
for i in range(n-1):
    for j in range(i+1,min(n,i+k+1)):
        c[j] = min(c[j],c[i]+abs(a[i]-a[j]))
print(c[n-1])
Buggy python submission (verdict: Runtime Error):
n = int(input())
a = []
b = []
for _ in range(n):
    a.append(list(map(int,input().split())))
    d.append([0,0,0])
d[0]=a[0]
for i in range(1,n):
    for j in range(3):
        d[i][j]=max(d[i-1][(j+1)%3],d[i-1][(j+2)%3])+a[i][j]
print(max(d[n-1]))


Fixed submission:
n = int(input())
a = []
d = []
for _ in range(n):
    a.append(list(map(int,input().split())))
    d.append([0,0,0])
d[0]=a[0]
for i in range(1,n):
    for j in range(3):
        d[i][j]=max(d[i-1][(j+1)%3],d[i-1][(j+2)%3])+a[i][j]
print(max(d[-1]))
Buggy python submission (verdict: Time Limit Exceeded):
n,w = map(int,input().split())
v = []
wt = []
for _ in range(n):
    x,y=map(int,input().split())
    wt.append(x)
    v.append(y)
a = [[0 for x in range(w+1)] for x in range(n+1)] 
for i in range(n+1):
    for j in range(w+1):
        if i == 0 or j==0:
            a[i][j]=0
        elif wt[i-1]<=j:
            a[i][j]=max(a[i-1][j],(v[i-1]+a[i-1][j-wt[i-1]]))
        else:
            a[i][j]=a[i-1][j]
print(a[n][w])

Fixed submission:
n,w = map(int,input().split())
v = []
wt = []
for _ in range(n):
    x,y=map(int,input().split())
    wt.append(x)
    v.append(y)
a = [[0 for x in range(w+1)] for x in range(n+1)] 
for i in range(n+1):
    for j in range(w+1):
        if i == 0 or j==0:
            a[i][j]=0
        elif wt[i-1]<=j:
            a[i][j]=max(a[i-1][j],(v[i-1]+a[i-1][j-wt[i-1]]))
        else:
            a[i][j]=a[i-1][j]
print(a[n][w])
Buggy python submission (verdict: Runtime Error):
n=int(input())
a=[0]*(n-1)
b=[0]*(n-1)
c=[0]*(n-1)
for _ in range(n-1):
    a,b,c=map(int,input().split())

dp=[[0]*3 for _ in range(n)]

dp[0] = [a[0],b[0],c[0]]

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

Fixed submission:
n=int(input())
a=[0]*(n)
b=[0]*(n)
c=[0]*(n)
for _ in range(n):
    a[_],b[_],c[_]=map(int,input().split())

dp=[[0]*3 for _ in range(n)]

dp[0] = [a[0],b[0],c[0]]

for i in range(n-1):
    dp[i+1][0]=max(dp[i][1]+a[i+1], dp[i][2]+a[i+1])
    dp[i+1][1]=max(dp[i][0]+b[i+1], dp[i][2]+b[i+1])
    dp[i+1][2]=max(dp[i][0]+c[i+1], dp[i][1]+c[i+1])
print(max(dp[n-1]))
Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
p=list(map(float,input().split()))
#dp[i][j] i tells u i coins from 0, j tells u j heads 
#dp[n+1][n+1]
dp=[[0 for i in range(0,n+1)]for j in range(n+1)]

dp[0][0]=1.0
# for i in range(1,n+1):
#     dp[0][i]=0.0
for i in range(1,n+1):
    for j in range(0,n+1):
        if(j==0):
            dp[i][j]=(1.0-p[i-1])*dp[i-1][j]
        else:
            dp[i][j]=p[i-1]*dp[i-1][j-1]+(1.0-p[i-1])*dp[i-1][j]

k=(n//2)+1
ans=0.0
for i in range(k,n+1):
    ans+=dp[n][i]
print(ans)




Fixed submission:
n=int(input())
p=list(map(float,input().split()))
#dp[i][j] i tells u i coins from 0, j tells u j heads 
#dp[n+1][n+1]
dp=[[0 for i in range(n+1)]for j in range(n+1)]

dp[0][0]=1.0
# for i in range(1,n+1):
#     dp[0][i]=0.0
for i in range(1,n+1):
    for j in range(0,n+1):
        if(j==0):
            dp[i][j]=(1.0-p[i-1])*dp[i-1][j]
        else:
            dp[i][j]=p[i-1]*dp[i-1][j-1]+(1.0-p[i-1])*dp[i-1][j]

k=(n//2)+1
ans=0.0
for i in range(k,n+1):
    ans+=dp[n][i]
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n, k = list(map(int,input().split()))
l = list(map(int,input().split()))
dp = [10**10]*n
dp[0] = 0
dp[1] = abs(l[0] - l[1])
for i in range(2,n):
    for j in range(i-1,max(0,i-k)-1,-1):
        tem = dp[j] + abs(l[i] - l[j])
        if tem<dp[i]:
            dp[i] = tem
    
print(dp[n-1])
#print(dp)    
    

Fixed submission:
n, k = list(map(int,input().split()))
l = list(map(int,input().split()))
dp = [10**9]*n
dp[0] = 0
dp[1] = abs(l[0] - l[1])
for i in range(2,n):
    for j in range(i-1,max(0,i-k)-1,-1):
        tem = dp[j] + abs(l[i] - l[j])
        if tem<dp[i]:
            dp[i] = tem
    
print(dp[n-1])

Buggy python submission (verdict: Time Limit Exceeded):
n, k = list(map(int,input().split()))
l = list(map(int,input().split()))
dp = [0]*n
dp[1] = abs(l[0] - l[1])
for i in range(2,n):
    tem = []
    for j in range(i-1,max(0,i-k)-1,-1):
        tem.append(dp[j] + abs(l[i] - l[j]))
    dp[i] = min(tem)
    
print(dp[n-1])
    
    

Fixed submission:
n, k = list(map(int,input().split()))
l = list(map(int,input().split()))
dp = [10**9]*n
dp[0] = 0
dp[1] = abs(l[0] - l[1])
for i in range(2,n):
    for j in range(i-1,max(0,i-k)-1,-1):
        tem = dp[j] + abs(l[i] - l[j])
        if tem<dp[i]:
            dp[i] = tem
    
print(dp[n-1])
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
l = list(map(float,input().split()))
dp = [[0 for _ in range(n+1)] for j in range(n+1)]
dp[0][0] = 1
for i in range(1,n+1):
    dp[i][0] = dp[i-1][0]*(1-l[i-1])
for i in range(1,n+1):
    for j in range(1,n+1):
        dp[i][j] = dp[i-1][j]*(1-l[i-1]) + dp[i-1][j-1]*l[i-1]
ans = 0
for i in range(n//2+1,n+1):
    ans+=dp[n][i]
print(ans)

Fixed submission:
n = int(input())
l = list(map(float,input().split()))
dp = [[0 for _ in range(n+1)] for j in range(n+1)]
dp[0][0] = 1
for i in range(1,n+1):
    dp[i][0] = dp[i-1][0]*(1-l[i-1])
for i in range(1,n+1):
    for j in range(1,n+1):
        dp[i][j] = dp[i-1][j]*(1-l[i-1]) + dp[i-1][j-1]*l[i-1]
ans = 0
for i in range(n//2+1,n+1):
    ans+=dp[n][i]
print(ans)