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

A = [1,0]
AB = 0
ABC = 0
D = 10**9 + 7
for c in s:
    if c == 'A':
        A[1] += A[0]
    elif c == 'B':
        AB += A[1]
    elif c == 'C':
        ABC += AB
    elif c == '?':
        ABC = (((ABC)%D *3)%D + (AB)%D)%D
        AB *= 3#AB + C and AB + B and AB + C
        AB += A[1] # AB + B
        A[1] = A[1]*3 + A[0]
        A[0] *= 3

print(ABC%D) 


Fixed submission:
s = input()

A = [1,0]
AB = 0
ABC = 0
D = 10**9 + 7
for c in s:
    if c == 'A':
        A[1] += A[0]
    elif c == 'B':
        AB += A[1]
    elif c == 'C':
        ABC += AB
    elif c == '?':
        ABC = (((ABC%D) *3)%D + (AB)%D)%D
        AB = (((AB%D) *3)%D + (A[1])%D)%D
        A[1] = (((A[1]%D)*3)%D + A[0]%D)%D
        A[0] = ((A[0]%D) * 3)%D

print(ABC%D)

Buggy python submission (verdict: Time Limit Exceeded):
s = input()

A = [1,0]
AB = 0
ABC = 0
D = 10**9 + 7
for c in s:
    if c == 'A':
        A[1] += A[0]
    elif c == 'B':
        AB += A[1]
    elif c == 'C':
        ABC += AB
    elif c == '?':
        ABC = ABC*3 + AB
        AB *= 3#AB + C and AB + B and AB + C
        AB += A[1] # AB + B
        A[1] = A[1]*3 + A[0]
        A[0] *= 3

print(ABC%D) 


Fixed submission:
s = input()

A = [1,0]
AB = 0
ABC = 0
D = 10**9 + 7
for c in s:
    if c == 'A':
        A[1] += A[0]
    elif c == 'B':
        AB += A[1]
    elif c == 'C':
        ABC += AB
    elif c == '?':
        ABC = (((ABC%D) *3)%D + (AB)%D)%D
        AB = (((AB%D) *3)%D + (A[1])%D)%D
        A[1] = (((A[1]%D)*3)%D + A[0]%D)%D
        A[0] = ((A[0]%D) * 3)%D

print(ABC%D)
Buggy python submission (verdict: Time Limit Exceeded):
s = input()
K = int(input())

d = dict()
SET = set()
for i in range(len(s)):
    if not d.__contains__(s[i]):
        d[s[i]] = []
    d[s[i]].append(i)


alphabet = 'abcdefjhijklmnopqrstuvwxyz'

for c in alphabet:
    if not d.__contains__(c):
        continue
    l = d[c].copy()
    SET.add(c)
    if(len(SET) >= K):
        break
    tmp = []
    for idx in l:
        if idx+1>=len(s):
            continue
        tmp.append((idx,s[idx+1]))
    tmp.sort(key = lambda x:x[1])
    for idx,nxt in tmp:
        for step in range(2,len(s)+1):
            if idx+step>len(s):
                break
            if s[idx:idx+step] not in SET:
                SET.add(s[idx:idx+step])
    if len(SET) >= K:
         break

res = list(SET)
res.sort()
print(res[K-1])


Fixed submission:
s = input()
K = int(input())

d = dict()
SET = set()
for i in range(len(s)):
    if not d.__contains__(s[i]):
        d[s[i]] = []
    d[s[i]].append(i)


alphabet = 'abcdefjhijklmnopqrstuvwxyz'

for c in alphabet:
    if not d.__contains__(c):
        continue
    l = d[c].copy()
    SET.add(c)
    if(len(SET) >= K):
        break
    tmp = []
    for idx in l:
        if idx+1>=len(s):
            continue
        tmp.append((idx,s[idx+1:len(s)]))
    tmp.sort(key = lambda x:x[1])
    for idx,nxt in tmp:
        for step in range(2,len(s)+1):
            if idx+step>len(s):
                break
            if s[idx:idx+step] not in SET:
                SET.add(s[idx:idx+step])
                if len(SET) >= K:
                    break
        if len(SET) >= K:
            break
    if len(SET) >= K:
         break

res = list(SET)
res.sort()
print(res[K-1])
Buggy python submission (verdict: Runtime Error):
import itertools

s = input()

x = ['+','-']

l = list(itertools.product(x,x,x))

res = int(s[0])
for sign in l:
  res = int(s[0])
  for i in range(3):
    if sign[i] == '+':
      res += int(s[i+1])
    else:
      res -= int(s[i+1])
  if res == 7:
    print(s[0],end="")
    for i in range(3):
      print(sign[i],end="")
      print(s[i+1],end="")
    print("=7")
	exit(0)

Fixed submission:
import itertools

s = input()

x = ['+','-']

l = list(itertools.product(x,x,x))

res = int(s[0])
for sign in l:
  res = int(s[0])
  for i in range(3):
    if sign[i] == '+':
      res += int(s[i+1])
    else:
      res -= int(s[i+1])
  if res == 7:
    print(s[0],end="")
    for i in range(3):
      print(sign[i],end="")
      print(s[i+1],end="")
    print("=7")
    exit(0)
Buggy python submission (verdict: Time Limit Exceeded):
k = int(input())

a = [0]*(10**6)
for i in range(10**6):
    a[i] = sum([int(c) for c in str(k*(i+1))])

print(min(a))


Fixed submission:
from collections import deque
k = int(input())
d = deque()
mat = []
for i in range(k):
    mat.append([])
#mark = [False]*k
dis = [10**18]*k
dis[1] = 0
for i in range(k):
    mat[i].append(((i+1)%k,True))

    if (10*i)%k != i:
        mat[i].append(((10*i)%k,False))

#bfs 1->0
d.append(1)
res = 0
while d:
    left = d.popleft()
    for neighbour,edge in mat[left]:
        distance = edge + dis[left]
        if dis[neighbour] > distance: 
            dis[neighbour] = distance 
            
            if edge == 0:
                d.appendleft(neighbour)
            else:
                d.append(neighbour)
print(dis[0]+1)
Buggy python submission (verdict: Runtime Error):
import math
n = int(input())

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

s = 0

for i in range(n):
    s += data[i]
    data[i] = s

a = data[-1]
res = math.inf
for i in range(n-1):
    res = min(res,abs(data[i]-(a-data[i])))
print(res)


Fixed submission:
n = int(input())

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

s = 0

for i in range(n):
    s += data[i]
    data[i] = s

a = data[-1]
res = -1
for i in range(n-1):
    if res<0:
        res = abs(data[i]-(a-data[i]))
    else:
        res = min(res,abs(data[i]-(a-data[i])))
print(res)
Buggy python submission (verdict: Time Limit Exceeded):
n,a,b = map(int,input().split())

h = []
for i in range(n):
    h.append(int(input()))
st,ed = 0,10**9+1
hc = [0]*n
while st<ed-1:
    mid = (st+ed)//2
    #print(mid)
    tmp = 0
    for i in range(n):
        hc[i]=h[i]-mid*b
    for i in range(n):
        if hc[i]>0:
            tmp+=(hc[i]//(a-b))+(hc[i]%(a-b)>0)
    if tmp<=mid:
        ed = mid
    else:
        st = mid
print(ed) 


Fixed submission:
n,a,b = map(int,input().split())

h = []
for i in range(n):
    h.append(int(input()))
st,ed = 0,10**9+1
while st<ed-1:
    mid = (st+ed)//2
    #print(mid)
    tmp = 0
    for i in range(n):
        x = h[i]-mid*b
        if x>0:
            tmp+=(x//(a-b))+(x%(a-b)>0)
    if tmp<=mid:
        ed = mid
    else:
        st = mid
print(ed)

Buggy python submission (verdict: Time Limit Exceeded):
n,a,b = map(int,input().split())

h = []
for i in range(n):
    h.append(int(input()))
hc = [0]*n
st,ed = 0,10**9+1
while st<ed-1:
    mid = (st+ed)//2
    #print(mid)
    tmp = 0
    for i in range(n):
        hc[i]=h[i]-mid*b
    for i in range(n):
        tmp+=(hc[i]//(a-b))+(hc[i]%(a-b)>0)
    if tmp<=mid:
        ed = mid
    else:
        st = mid
print(ed) 


Fixed submission:
n,a,b = map(int,input().split())

h = []
for i in range(n):
    h.append(int(input()))
st,ed = 0,10**9+1
while st<ed-1:
    mid = (st+ed)//2
    #print(mid)
    tmp = 0
    for i in range(n):
        x = h[i]-mid*b
        if x>0:
            tmp+=(x//(a-b))+(x%(a-b)>0)
    if tmp<=mid:
        ed = mid
    else:
        st = mid
print(ed)
Buggy python submission (verdict: Time Limit Exceeded):
import queue
x = int(input())

q = queue.Queue()
q.put((0,0))
d = dict()
d[0] = 0
while not q.empty():
    s,t = q.get()
    if s==x:
        break
    if not d.__contains__(s-(t+1)):
        q.put((s-(t+1),t+1))
        d[s-(t+1)]=t+1
    if not d.__contains__(s+t+1):
        q.put((s+t+1,t+1))
        d[s+t+1]=t+1
    q.put((s,t+1))
print(d[x])


Fixed submission:
x = int(input())
s = 0
i = 0
for i in range(1,10**9):
    s += i
    if s>=x:
        break
print(i)
Buggy python submission (verdict: Runtime Error):
n = int(input())
dat = list(map(int,input().split()))

cnt = dict()

for d in dat:
    if cnt.__contains__(d):
        cnt[d]+=1
    else:
        cnt[d]=1

if n%2:
    if cnt[0] != 1:
        print(0)
        exit(0)
    for i in range(2,n,2):
        if cnt[i] != 2:
            print(0)
            exit(0)
else:
    for i in range(1,n,2):
        if cnt[i] != 2:
            print(0)
            exit(0)
print(2**(n//2))


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

cnt = dict()

for i in range(n):
    cnt[i] = 0
for d in dat:
    cnt[d]+=1

if n%2:
    if cnt[0] != 1:
        print(0)
        exit(0)
    for i in range(2,n,2):
        if cnt[i] != 2:
            print(0)
            exit(0)
else:
    for i in range(1,n,2):
        if cnt[i] != 2:
            print(0)
            exit(0)
print((2**(n//2))%1000000007)
Buggy python submission (verdict: Time Limit Exceeded):
N, K = map(int, input().split())

e_table = [0]
pre = 0
for i in range(1,1001):
    e_table.append((pre + i)/i)
    pre = pre + i

lis = [0] * K

maximam = 0

for p in input().split():
    p = int(p)
    lis = lis[1:]
    lis.append(e_table[p])
    maximam = max(maximam, sum(lis))
print(maximam)

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

e_table = [0]
pre = 0
for i in range(1,1001):
    e_table.append((pre + i)/i)
    pre = pre + i

lis = [0] * K
SUM = 0
maximam = 0

for i, p in enumerate(input().split()):
    p = int(p)
    lis.append(e_table[p])
    SUM = SUM - lis[i] + lis[-1]
    maximam = max(maximam, SUM)
print(maximam)
Buggy python submission (verdict: Runtime Error):
import math
A, B, C, D = map(int, input().split())
diff = B - A + 1
count_c = int(B/C) - int((A-1)/C)
count_d = int(B/D) - int((A-1)/D)
cd = (C*D) // math.gcd(C,D)
count_cd = int(B/cd) - int((A-1)/cd)
print(diff - count_c - count_d + count_cd)

Fixed submission:
def gcd(a, b):
	while b:
		a, b = b, a % b
	return a
def lcm(a, b):
	return a * b // gcd (a, b)
A, B, C, D = map(int, input().split())
diff = B - A + 1
count_c = B//C - (A-1)//C
count_d = B//D - (A-1)//D
cd = lcm(C,D)
count_cd = B//cd - (A-1)//cd
print(diff - count_c - count_d + count_cd)
Buggy python submission (verdict: Runtime Error):
from collections import Counter
N = int(input())
XY = []
XY_cand = []
for _ in range(N):
        x, y = map(int, input().split())
        XY.append((x,y))
for (x, y) in XY:
        for (i, j) in XY:
                if i != x or j != y:
                        XY_cand.append((i-x, j-y))
print(N - Counter(XY_cand).most_common()[0][1])

Fixed submission:
from collections import Counter
N = int(input())
XY = []
XY_cand = []
for _ in range(N):
        x, y = map(int, input().split())
        XY.append((x,y))
for (x, y) in XY:
        for (i, j) in XY:
                if i != x or j != y:
                        XY_cand.append((i-x, j-y))
if XY_cand == []:
        print(N)
else:
        print(N - Counter(XY_cand).most_common()[0][1])
Buggy python submission (verdict: Time Limit Exceeded):
N, M = map(int, input().split())
A = sorted([int(a) for a in input().split()])
for num in range(M):
    b, c = map(int, input().split())
    b = min(b, N)
    if A[-1] < c:
        if b == N:
            A = [c] * b
        else:
            A = A[b:] + [c] * b
    elif A[0] < c:
        for index, a in enumerate(A):
            if a >= c:
                A = A[:index] + [c] * b + A[index:]
                A = A[b:]
                break
total = 0
for a in A:
    total += a
print(total)

Fixed submission:
N, M = map(int, input().split())
A = sorted([int(a) for a in input().split()])[::-1]
BC = []
for num in range(M):
    b, c = map(int, input().split())
    BC.append((b, c))
lis = sorted(BC, key = lambda x: -x[1])
total = 0
counter = 0
while counter < N:
    if not lis == []:
        if lis[0][1] > A[0]:
            (b, c) = lis.pop(0)
            b = min(b, N - counter)
            total += c * b
            counter += b
        else:
            total += A.pop(0)
            counter += 1
    else:
        total += A.pop(0)
        counter += 1
print(total)

Buggy python submission (verdict: Time Limit Exceeded):
N, M = map(int, input().split())
A = sorted([int(a) for a in input().split()])
for num in range(M):
    b, c = map(int, input().split())
    b = min(b, N)
    if A[-1] < c:
        if b == N:
            A = [c] * b
        else:
            A = A[b:] + [c] * b
    elif A[0] < c:
        A += [c] * b
        A = sorted(A)[b:]
total = 0
for a in A:
    total += a
print(total)

Fixed submission:
N, M = map(int, input().split())
A = sorted([int(a) for a in input().split()])[::-1]
BC = []
for num in range(M):
    b, c = map(int, input().split())
    BC.append((b, c))
lis = sorted(BC, key = lambda x: -x[1])
total = 0
counter = 0
while counter < N:
    if not lis == []:
        if lis[0][1] > A[0]:
            (b, c) = lis.pop(0)
            b = min(b, N - counter)
            total += c * b
            counter += b
        else:
            total += A.pop(0)
            counter += 1
    else:
        total += A.pop(0)
        counter += 1
print(total)
Buggy python submission (verdict: Time Limit Exceeded):
def euclid(a, b):
    mod = a % b
    if mod != 0:
        b = euclid(b, mod)
    return b
N = int(input())
A = [int(a) for a in input().split()]
gcd_lis = []
for i in range(N):
    X = A[:i]+A[i+1:]
    gcd = X[0]
    for x in X:
        gcd = euclid(gcd, x)
    gcd_lis.append(gcd)
maximam = 1
for j in gcd_lis:
    maximam = max(maximam, j)
print(maximam)

Fixed submission:
def euclid(a, b):
    mod = a % b
    if mod != 0:
        b = euclid(b, mod)
    return b
N = int(input())
A = [int(a) for a in input().split()]
gcd_lis = [A[0]]
gcd = A[0]
for a in A[1:]:
    gcd = euclid(gcd, a)
    gcd_lis.append(gcd)
inv_gcd_lis = [A[-1]]
gcd = A[-1]
for a in A[::-1][1:]:
    gcd = euclid(gcd, a)
    inv_gcd_lis.append(gcd)
inv_gcd_lis = inv_gcd_lis[::-1]
maximam = 0
for index in range(N):
    if index == 0:
        gcd = inv_gcd_lis[1]
    elif index == N - 1:
        gcd = gcd_lis[N-2]
    else:
        gcd = euclid(gcd_lis[index - 1], inv_gcd_lis[index + 1])
    maximam = max(gcd, maximam)
print(maximam)
Buggy python submission (verdict: Runtime Error):
inf = 10**20
n, k = map(int, input().split())
hs = [int(s) for s in input().split()]

dp = [inf] * n
dp[0] = 0

for i in range(1, n):
    for j in range(i-1, max(0, i-k)-1, -1):
        dp[i] = min(dp[j] + abs(hs[i] - hs[j]), dp[i])
print(dp[-1])

Fixed submission:
n = int(input())
hs = [int(s) for s in input().split()]
dp = [0]*n
dp[0], dp[1] = 0, abs(hs[1]-hs[0])
for i in range(2, n):
  dp[i] = min(dp[i-1] + abs (hs[i] - hs[i-1]), dp[i-2] + abs(hs[i] - hs[i-2]))
print(dp[-1])

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

Fixed submission:
n = int(input())
hs = [int(s) for s in input().split()]
dp = [0]*n
dp[0], dp[1] = 0, abs(hs[1]-hs[0])
for i in range(2, n):
  dp[i] = min(dp[i-1] + abs (hs[i] - hs[i-1]), dp[i-2] + abs(hs[i] - hs[i-2]))
print(dp[-1])

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

Fixed submission:
n = int(input())
hs = [int(s) for s in input().split()]
dp = [0]*n
dp[0], dp[1] = 0, abs(hs[1]-hs[0])
for i in range(2, n):
  dp[i] = min(dp[i-1] + abs (hs[i] - hs[i-1]), dp[i-2] + abs(hs[i] - hs[i-2]))
print(dp[-1])
Buggy python submission (verdict: Time Limit Exceeded):
N, K = map(int, input().split())
H = [int(h) for h in input().split()]
dp = [N*10**4]*N
dp[0] = 0
for i in range(N):
        x = min(i+K+1, N)
        for j in range(i+1, x):
                dp[j] = min(dp[j], dp[i] + abs(H[i]-H[j]))
print(dp[N-1])

Fixed submission:
inf = 10**20
n, k = map(int, input().split())
hs = [int(s) for s in input().split()]
 
dp = [inf] * n
dp[0] = 0
 
for i in range(1, n):
    for j in range(i-1, max(0, i-k)-1, -1):
        dp[i] = min(dp[j] + abs(hs[i] - hs[j]), dp[i])
print(dp[-1])

Buggy python submission (verdict: Time Limit Exceeded):
N, K = map(int, input().split())
H = [int(h) for h in input().split()]
dp = [N*10**4]*N
dp[0] = 0
for i in range(1,N):
    x = max(0, i-K)
    minimam = N*10**4
    for j in range(x, i):
        if i == 1:
            minimam = dp[0] + abs(H[i]-H[i-1])
        minimam = min(minimam, dp[j] + abs(H[i]-H[j]))
    dp[i] = minimam
print(dp[N-1])

Fixed submission:
inf = 10**20
n, k = map(int, input().split())
hs = [int(s) for s in input().split()]
 
dp = [inf] * n
dp[0] = 0
 
for i in range(1, n):
    for j in range(i-1, max(0, i-k)-1, -1):
        dp[i] = min(dp[j] + abs(hs[i] - hs[j]), dp[i])
print(dp[-1])

Buggy python submission (verdict: Time Limit Exceeded):
inf = 10**20
n, k = map(int, input().split())
hs = [int(s) for s in input().split()]

dp = [inf] * n
dp[0] = 0

for i in range(1, n):
    for j in range(i-1, max(0, i-k)-1, -1):
        dp[i] = min(dp[j] + abs(hs[i] - hs[j]), dp[i])
print(dp[-1])

Fixed submission:
inf = 10**20
n, k = map(int, input().split())
hs = [int(s) for s in input().split()]
 
dp = [inf] * n
dp[0] = 0
 
for i in range(1, n):
    for j in range(i-1, max(0, i-k)-1, -1):
        dp[i] = min(dp[j] + abs(hs[i] - hs[j]), dp[i])
print(dp[-1])
Buggy python submission (verdict: Runtime Error):
N = int(input())
for i in range(N):
        a,b,c = map(int,input().split())
        if i == 0:
                preA = a
                preB = b
                preC = c
        else:
                A = max(preB + a, preC + a)
                B = max(preA + b, preC + b)
                C = max(preA + c, preB + c)
                preA = A
                preB = B
                preC = C
print(max(A, B, C))

Fixed submission:
abc = []
n = int(input())
for i in range(n):
  abc.append([int(s) for s in input().split()])

dp = [[0, 0, 0]for i in range(n)]
dp[0][0] = abc[0][0]
dp[0][1] = abc[0][1]
dp[0][2] = abc[0][2]
for i in range(1, n):
  dp[i][0] = max(dp[i-1][1]+abc[i][0], dp[i-1][2]+abc[i][0])
  dp[i][1] = max(dp[i-1][0]+abc[i][1], dp[i-1][2]+abc[i][1])
  dp[i][2] = max(dp[i-1][0]+abc[i][2], dp[i-1][1]+abc[i][2])
print(max(dp[n-1]))
Buggy python submission (verdict: Time Limit Exceeded):
N, W = map(int, input().split())
dp = [[0]*(W+1) for _ in range(N+1)]
for j in range(1, N+1):
        w, v = map(int, input().split())
        for k in range(1, W+1):
                if k < w:
                        dp[j][k] = dp[j-1][k]
                else:
                        dp[j][k] = max(dp[j-1][k-w]+v, dp[j-1][k])
print(dp[N][W])

Fixed submission:
N, W = map(int, input().split())
val = [0]*(W+1)
for i in range(N):
  w, v = map(int, input().split())
  for j in reversed(range(w,W+1)):
    val[j] = max(val[j], val[j-w] + v) 
print(val[W])

Buggy python submission (verdict: Time Limit Exceeded):
N, W = map(int, input().split())
val = [0]*(W+1)
for i in range(N):
  w, v = map(int, input().split())
  for j in reversed(range(w,W+1)):
    val[j] = max(val[j], val[j-w] + v) 
print(val[W])

Fixed submission:
N, W = map(int, input().split())
val = [0]*(W+1)
for i in range(N):
  w, v = map(int, input().split())
  for j in reversed(range(w,W+1)):
    val[j] = max(val[j], val[j-w] + v) 
print(val[W])
Buggy python submission (verdict: Runtime Error):
N, W = map(int, input().split())
val = [0]*(W+1)
for i in range(N):
  w, v = map(int, input().split())
  for j in reversed(range(w,W+1)):
    val[j] = max(val[j], val[j-w] + v) 
print(val[W])

Fixed submission:
N, W = map(int, input().split())
max_value = N*(10**3)
dp = [[10**11]*(max_value+1) for _ in range(N+1)]
dp[0][0]=0
for j in range(1, N+1):
    w, v = map(int, input().split())
    for k in range(0, max_value+1):
        if k < v:
            dp[j][k] = dp[j-1][k]
        else:
            dp[j][k] = min(dp[j-1][k-v]+w, dp[j-1][k])
answer = 0
for index, weight in enumerate(dp[N]):
    if weight <= W:
        answer = index
print(answer)

Buggy python submission (verdict: Runtime Error):
N, W = map(int, input().split())
val = [0]*(W+1)
for i in range(N):
  w, v = map(int, input().split())
  for j in reversed(range(w,W+1)):
    val[j] = max(val[j], val[j-w] + v) 
print(val[W])

Fixed submission:
N, W = map(int, input().split())
max_value = N*(10**3)
dp = [[10**11]*(max_value+1) for _ in range(N+1)]
dp[0][0]=0
for j in range(1, N+1):
    w, v = map(int, input().split())
    for k in range(0, max_value+1):
        if k < v:
            dp[j][k] = dp[j-1][k]
        else:
            dp[j][k] = min(dp[j-1][k-v]+w, dp[j-1][k])
answer = 0
for index, weight in enumerate(dp[N]):
    if weight <= W:
        answer = index
print(answer)
Buggy python submission (verdict: Runtime Error):
def lp(node,memo,graph):
    if memo[node] != -1:
        return memo[node]
    cand = [0]
    if graph[node]:
        for neighbor in graph[node]:
            cand.append(lp(neighbor,memo,graph))
        maximam = max(cand)+1
    else:
        maximam = 0
    memo[node]=maximam
    return maximam

import sys
sys.setrecursionlimit(10**10)
N,M = map(int, input().split())
graph = {}
for i in range(N+1):
    graph[i] = []
for _ in range(M):
    x,y = map(int,input().split())
    graph[x].append(y)
ans = 0
memo = [-1]*(N+1)
for i in range(1,N+1):
    ans = max(ans, lp(i,memo,graph))
print(ans)

Fixed submission:
def lp(node,memo,graph):
    if memo[node] != -1:
        return memo[node]
    cand = [0]
    if graph[node]:
        for neighbor in graph[node]:
            cand.append(lp(neighbor,memo,graph))
        maximam = max(cand)+1
    else:
        maximam = 0
    memo[node]=maximam
    return maximam

import sys
sys.setrecursionlimit(10**5)
N,M = map(int, input().split())
graph = {}
for i in range(N+1):
    graph[i] = []
for _ in range(M):
    x,y = map(int,input().split())
    graph[x].append(y)
ans = 0
memo = [-1]*(N+1)
for i in range(1,N+1):
    ans = max(ans, lp(i,memo,graph))
print(ans)

Buggy python submission (verdict: Runtime Error):
def lp(node,memo,graph):
    if memo[node] != -1:
        return memo[node]
    cand = [0]
    if graph[node]:
        for neighbor in graph[node]:
            cand.append(lp(neighbor,memo,graph))
        maximam = max(cand)+1
    else:
        maximam = 0
    memo[node]=maximam
    return maximam

N,M = map(int, input().split())
graph = {}
for i in range(N+1):
    graph[i] = []
for _ in range(M):
    x,y = map(int,input().split())
    graph[x].append(y)
ans = 0
memo = [-1]*(N+1)
for i in range(1,N+1):
    ans = max(ans, lp(i,memo,graph))
print(ans)

Fixed submission:
def lp(node,memo,graph):
    if memo[node] != -1:
        return memo[node]
    cand = [0]
    if graph[node]:
        for neighbor in graph[node]:
            cand.append(lp(neighbor,memo,graph))
        maximam = max(cand)+1
    else:
        maximam = 0
    memo[node]=maximam
    return maximam

import sys
sys.setrecursionlimit(10**5)
N,M = map(int, input().split())
graph = {}
for i in range(N+1):
    graph[i] = []
for _ in range(M):
    x,y = map(int,input().split())
    graph[x].append(y)
ans = 0
memo = [-1]*(N+1)
for i in range(1,N+1):
    ans = max(ans, lp(i,memo,graph))
print(ans)
Buggy python submission (verdict: Runtime Error):
N = int(input())
A = [0]*(2*10**5+1)
A[0] = 1
total = 0
count = 0
for a in input().split():
    total += int(a)
    count += A[total] 
    A[total] += 1
print(count)

Fixed submission:
N = int(input())
A = {0:1}
total = 0
count = 0
for a in input().split():
    total += int(a)
    if total in A:
        count += A[total]
        A[total] += 1
    else:
        A[total] = 1
print(count)

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = [0]
total = 0
count = 0
for a in input().split():
    total += int(a)
    for b in A:
        if b == total:
            count += 1 
    A.append(total)
print(count)

Fixed submission:
N = int(input())
A = {0:1}
total = 0
count = 0
for a in input().split():
    total += int(a)
    if total in A:
        count += A[total]
        A[total] += 1
    else:
        A[total] = 1
print(count)