Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
import copy
import bisect
from collections import deque

def dfs(i, k, v, x):
    if i >= k:
        return sum(x)
    y = [0, 0, 0, 0]
    if len(v) > 0:
        p = v.popleft()
        xi = copy.copy(x)
        bisect.insort(xi, p)
        y[0] = dfs(i + 1, k, v, xi)
        v.appendleft(p)
    if len(v) > 1:
        p = v.pop()
        xi = copy.copy(x)
        bisect.insort(xi, p)
        y[1] = dfs(i + 1, k, v, xi)
        v.append(p)
    if len(x) > 0:
        p = x[0]
        xi = copy.copy(x)
        del xi[0]
        v.appendleft(p)
        y[2] = dfs(i + 1, k, v, xi)
        _ = v.popleft()
        v.append(p)
        y[3] = dfs(i + 1, k, v, xi)
        _ = v.pop()
    return max(y)

n, k = map(int, input().split())
v = deque(list(map(int, input().split())))
x = []
ans = dfs(0, k, v, [])
print(ans)


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

ans = 0
if n == 1:
    ans = max(0, v[0])
else:
    ans = 0 if k < n else sum(v)
    for i in range(min(k + 1, n)):
        for j in range(i + 1):
            t = v[:j]
            if j != i:
                t += v[j - i:]
            t.sort()
            for p in range(k - i):
                if len(t) > 0 and t[0] < 0:
                    t.pop(0)
                else:
                    break
            if len(t) == 0:
                t = [0]
            ans = max(ans, sum(t))
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
import copy
from collections import deque

def dfs(i, k, v, x):
    if i >= k:
        return sum(x)
    x.sort()
    y = [0, 0, 0, 0]
    if len(v) > 0:
        p = v.popleft()
        xi = copy.copy(x)
        xi.append(p)
        y[0] = dfs(i + 1, k, v, xi)
        v.appendleft(p)
    if len(v) > 1:
        p = v.pop()
        xi = copy.copy(x)
        xi.append(p)
        y[1] = dfs(i + 1, k, v, xi)
        v.append(p)
    if len(x) > 0:
        p = x[0]
        xi = [x[i] for i in range(1, len(x))]
        v.appendleft(p)
        y[2] = dfs(i + 1, k, v, xi)
        _ = v.popleft()
        v.append(p)
        y[3] = dfs(i + 1, k, v, xi)
        _ = v.pop()
    return max(y)

n, k = map(int, input().split())
v = deque(list(map(int, input().split())))
x = []
ans = dfs(0, k, v, [])
print(ans)


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

ans = 0
if n == 1:
    ans = max(0, v[0])
else:
    ans = 0 if k < n else sum(v)
    for i in range(min(k + 1, n)):
        for j in range(i + 1):
            t = v[:j]
            if j != i:
                t += v[j - i:]
            t.sort()
            for p in range(k - i):
                if len(t) > 0 and t[0] < 0:
                    t.pop(0)
                else:
                    break
            if len(t) == 0:
                t = [0]
            ans = max(ans, sum(t))
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import bisect

n, m = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
for j in range(m):
    b, c = map(int, input().split())
    idx = bisect.bisect_left(a, c)
    if idx >= b:
        a = a[b:idx] + [c] * b + a[idx:]
    else:
        a = [c] * idx + a[idx:]
print(sum(a))


Fixed submission:
import bisect

n, m = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
c = [None] * m
for j in range(m):
    c[j] = list(map(int, input().split()))
c.sort(key=lambda x: x[1], reverse=True)
k = 0
ans = 0
for i in range(n):
    if k >= m:
        ans += sum(a[i:])
        break
    if a[i] >= c[k][1]:
        ans += a[i]
    else:
        ans += c[k][1]
        c[k][0] -= 1
        if c[k][0] == 0:
            k += 1
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
import bisect

n, m = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
for j in range(m):
    b, c = map(int, input().split())
    idx = bisect.bisect_left(a, c)
    if idx >= b:
        a = a[b:idx] + [c for _ in range(b)] + a[idx:]
    else:
        a = [c for _ in range(idx)] + a[idx:]
print(sum(a))


Fixed submission:
import bisect

n, m = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
c = [None] * m
for j in range(m):
    c[j] = list(map(int, input().split()))
c.sort(key=lambda x: x[1], reverse=True)
k = 0
ans = 0
for i in range(n):
    if k >= m:
        ans += sum(a[i:])
        break
    if a[i] >= c[k][1]:
        ans += a[i]
    else:
        ans += c[k][1]
        c[k][0] -= 1
        if c[k][0] == 0:
            k += 1
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
n, m = map(int, input().split())
a = list(map(int, input().split()))
for j in range(m):
    a.sort()
    b, c = map(int, input().split())
    for i in range(b):
        if a[i] > c:
            break
        a[i] = c
print(sum(a))


Fixed submission:
import bisect

n, m = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
c = [None] * m
for j in range(m):
    c[j] = list(map(int, input().split()))
c.sort(key=lambda x: x[1], reverse=True)
k = 0
ans = 0
for i in range(n):
    if k >= m:
        ans += sum(a[i:])
        break
    if a[i] >= c[k][1]:
        ans += a[i]
    else:
        ans += c[k][1]
        c[k][0] -= 1
        if c[k][0] == 0:
            k += 1
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
r, g, b, n = map(int, input().split())
c = sorted([r, g, b])[::-1]
ans = 0
for i in range(n // c[0] + 1):
    for j in range((n - i * r) // c[1] + 1):
        x = n - i * c[0] - j * c[1]
        if x >= 0 and x % c[2] == 0:
            ans += 1
print(ans)


Fixed submission:
r, g, b, n = map(int, input().split())
c = sorted([r, g, b])[::-1]
ans = 0
for i in range(n // c[0] + 1):
    x = n - i * c[0]
    for j in range(x // c[1] + 1):
        y = x - j * c[1]
        if y < 0:
            break
        elif y % c[2] == 0:
            ans += 1
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
r, g, b, n = map(int, input().split())
ans = 0
for i in range(n // r + 1):
    for j in range(n // g + 1):
        x = n - i * r - j * g
        if x >= 0 and x % b == 0:
            ans += 1
print(ans)


Fixed submission:
r, g, b, n = map(int, input().split())
c = sorted([r, g, b])[::-1]
ans = 0
for i in range(n // c[0] + 1):
    x = n - i * c[0]
    for j in range(x // c[1] + 1):
        y = x - j * c[1]
        if y < 0:
            break
        elif y % c[2] == 0:
            ans += 1
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
from fractions import gcd
from functools import reduce

def gcd_list(x):
    return reduce(gcd, x)

n = int(input())
a = list(map(int, input().split()))
y = []
for i in range(n):
    if i == 0:
        x = a[1:]
    elif i == n - 1:
        x = a[:-1]
    else:
        x = a[:i] + a[i + 1:]
    y.append(gcd_list(x))
print(max(y))


Fixed submission:
def divisor(x):
    y = list()
    for i in range(1, int(x ** 0.5 + 1)):
        if x % i == 0:
            y.append(i)
            y.append(x // i)
    return y

n = int(input())
a = list(map(int, input().split()))
a.sort()
d0 = divisor(a[0])
d1 = divisor(a[1])
d = dict.fromkeys(d0 + d1)
ans = 1
for di in sorted(list(d.keys()))[::-1]:
    flag = False
    ans_flag = True
    for ai in a:
        if ai % di != 0:
            if flag:
                ans_flag = False
                break
            else:
                flag = True
    if ans_flag:
        ans = di
        break
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n, k = map(int, input().split())
s = input()
x = [0]
for si in s:
    if si == '1':
        if x[-1] >= 0:
            x[-1] += 1
        else:
            x.append(1)
    else:
        if x[-1] <= 0:
            x[-1] -= 1
        else:
            x.append(-1)
y = []
for i in range(len(x)):
    yi = 0
    ki = 0
    for j in range(i, len(x)):
        if x[j] > 0:
            yi += x[j]
        else:
            if ki >= k:
                break
            yi += -x[j]
            ki += 1
    y.append(yi)
    if ki < k:
        break
print(max(y))


Fixed submission:
n, k = map(int, input().split())
s = input()
x = [0]
for i in range(n - 1):
    if s[i:i + 2] in ['01', '10']:
        x.append(i + 1)
y = []
for i in range(len(x)):
    idx = i + 2 * k
    if s[x[i]] == '0':
        if i > 0:
            continue
    else:
        idx += 1

    if idx < len(x):
        y.append(x[idx] - x[i])
    else:
        y.append(n - x[i])
        break
print(max(y))
Buggy python submission (verdict: Time Limit Exceeded):
x, y, z, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))
c.sort(reverse=True)

p = [0 for _ in range(x * y)]
t = 0
for ai in a:
    for bi in b:
        p[t] = ai + bi
        t += 1
p.sort(reverse=True)
q = [0 for _ in range(k * z)]
t = 0
for pi in p[:k]:
    for ci in c[:k]:
        q[t] = pi + ci
        t += 1
q.sort(reverse=True)
for qi in q[:k]:
    print(qi)


Fixed submission:
x, y, z, kk = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))
a.sort(reverse=True)
b.sort(reverse=True)
c.sort(reverse=True)

p = []
for i in range(x):
    for j in range(y):
        for k in range(z):
            if (i + 1) * (j + 1) * (k + 1) <= kk:
                p.append(a[i] + b[j] + c[k])
            else:
                break
p.sort(reverse=True)
for i in range(kk):
    print(p[i])

Buggy python submission (verdict: Time Limit Exceeded):
x, y, z, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))

p = [0 for _ in range(x * y)]
t = 0
for ai in a:
    for bi in b:
        p[t] = ai + bi
        t += 1
p.sort(reverse=True)
q = [0 for _ in range(k * z)]
t = 0
for pi in p[:k]:
    for ci in c:
        q[t] = pi + ci
        t += 1
q.sort(reverse=True)
for qi in q[:k]:
    print(qi)


Fixed submission:
x, y, z, kk = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))
a.sort(reverse=True)
b.sort(reverse=True)
c.sort(reverse=True)

p = []
for i in range(x):
    for j in range(y):
        for k in range(z):
            if (i + 1) * (j + 1) * (k + 1) <= kk:
                p.append(a[i] + b[j] + c[k])
            else:
                break
p.sort(reverse=True)
for i in range(kk):
    print(p[i])

Buggy python submission (verdict: Time Limit Exceeded):
x, y, z, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))

p = []
for ai in a:
    for bi in b:
        p.append(ai + bi)
p.sort(reverse=True)
q = []
for pi in p[:k]:
    for ci in c:
        q.append(pi + ci)
q.sort(reverse=True)
for qi in q[:k]:
    print(qi)


Fixed submission:
x, y, z, kk = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))
a.sort(reverse=True)
b.sort(reverse=True)
c.sort(reverse=True)

p = []
for i in range(x):
    for j in range(y):
        for k in range(z):
            if (i + 1) * (j + 1) * (k + 1) <= kk:
                p.append(a[i] + b[j] + c[k])
            else:
                break
p.sort(reverse=True)
for i in range(kk):
    print(p[i])
Buggy python submission (verdict: Time Limit Exceeded):
s = list(input())
x = list(map(int, s))
i = 0
ans = 0
k = 0
if len(x) == 1:
    print(0)
else:
    while(True):
        if x[i] + x[i + 1] == 1:
            k += 1
            del x[i + 1], x[i]
        if i + 2 >= len(x):
            ans += k
            if k == 0 or len(x) <= 1:
                break
            k = 0
            i = 0
        else:
            i += 1
    print(ans * 2)


Fixed submission:
s = list(input())
x = list(map(int, s))
k = 0
for i in range(len(x)):
    if x[i] == 0:
        k += 1
print(2 * min(k, len(x) - k))

Buggy python submission (verdict: Runtime Error):
s = list(input())
x = list(map(int, s))
i = 0
ans = 0
k = 0
if len(x) == 1:
    print(0)
else:
    while(True):
        if x[i] + x[i + 1] == 1:
            k += 1
            del x[i + 1], x[i]
        if i + 2 >= len(x):
            ans += k
            if k == 0 or len(x) == 0:
                break
            k = 0
            i = 0
        else:
            i += 1
    print(ans * 2)


Fixed submission:
s = list(input())
x = list(map(int, s))
k = 0
for i in range(len(x)):
    if x[i] == 0:
        k += 1
print(2 * min(k, len(x) - k))

Buggy python submission (verdict: Runtime Error):
s = list(input())
x = list(map(int, s))
i = 0
ans = 0
k = 0
while(True):
    if x[i] + x[i + 1] == 1:
        k += 1
        del x[i + 1], x[i]
    if i + 2 >= len(x):
        ans += k
        if k == 0 or len(x) == 0:
            break
        k = 0
        i = 0
    else:
        i += 1
print(ans * 2)


Fixed submission:
s = list(input())
x = list(map(int, s))
k = 0
for i in range(len(x)):
    if x[i] == 0:
        k += 1
print(2 * min(k, len(x) - k))
Buggy python submission (verdict: Time Limit Exceeded):
def bisect_search(x, L):
    if x <= L[0]:
        return 0
    elif x > L[-1]:
        return len(L)

    idx = len(L) // 2
    if x <= L[idx]:
        y = bisect_search(x, L[:idx])
    else:
        y = idx + bisect_search(x, L[idx:])
    return y

a, b, q = map(int, input().split())
INF = 10 ** 11
s = [int(input()) for _ in range(a)]
t = [int(input()) for _ in range(b)]
x = [int(input()) for _ in range(q)]
s = [-INF] + s + [INF]
t = [-INF] + t + [INF]

ans = []
for xi in x:
    s_idx = bisect_search(xi, s)
    t_idx = bisect_search(xi, t)
    yi = []
    for j in range(2):
        sj = s[s_idx - j]
        for k in range(2):
            tk = t[t_idx - k]
            d = min(abs(xi - sj), abs(xi - tk)) + abs(sj - tk)
            yi.append(d)
    ans.append(min(yi))
for ansi in ans:
    print(ansi)


Fixed submission:
import bisect

a, b, q = map(int, input().split())
INF = 10 ** 11
s = [int(input()) for _ in range(a)]
t = [int(input()) for _ in range(b)]
x = [int(input()) for _ in range(q)]
s = [-INF] + s + [INF]
t = [-INF] + t + [INF]

ans = []
for xi in x:
    s_idx = bisect.bisect_left(s, xi)
    t_idx = bisect.bisect_left(t, xi)
    yi = []
    for j in range(2):
        sj = s[s_idx - j]
        for k in range(2):
            tk = t[t_idx - k]
            d = min(abs(xi - sj), abs(xi - tk)) + abs(sj - tk)
            yi.append(d)
    ans.append(min(yi))
for ansi in ans:
    print(ansi)
Buggy python submission (verdict: Runtime Error):
import math

n = int(input())
a = list(map(int, input().split()))
x = a[0]
for i in range(1, n):
    x = math.gcd(x, a[i])
print(x)

Fixed submission:
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

n = int(input())
a = list(map(int, input().split()))
x = a[0]
for i in range(1, n):
    x = gcd(x, a[i])
print(x)

Buggy python submission (verdict: Runtime Error):
from fraction import gcd

n = int(input())
a = list(map(int, input().split()))
x = a[0]
for i in range(1, n):
    x = gcd(x, a[i])
    if x == 1:
        break
print(x)


Fixed submission:
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

n = int(input())
a = list(map(int, input().split()))
x = a[0]
for i in range(1, n):
    x = gcd(x, a[i])
print(x)

Buggy python submission (verdict: Runtime Error):
import math

n = int(input())
a = list(map(int, input().split()))
x = a[0]
for i in range(1, n):
    x = math.gcd(x, a[i])
    if x == 1:
        break
print(x)

Fixed submission:
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

n = int(input())
a = list(map(int, input().split()))
x = a[0]
for i in range(1, n):
    x = gcd(x, a[i])
print(x)
Buggy python submission (verdict: Runtime Error):
n, m = map(int, input().split())
a = list(map(int, input().split()))
a.sort(reverse=True)
b = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
dp = [0 for _ in range(n + 1)]
INF = 10 ** 9
for i in range(1, n + 1):
    c = [dp[i - b[aj]] for aj in a if i >= b[aj]]
    if len(c) > 0:
        dp[i] = max(c) + 1
    else:
        dp[i] = -INF

x = n
i = 0
ans = ''
while(True):
    for aj in a:
        if dp[x - b[aj]] == dp[n] - i - 1:
            i += 1
            x -= b[aj]
            ans += str(aj)
            break
    if i == dp[n]:
        break
print(ans)


Fixed submission:
n, m = map(int, input().split())
a = list(map(int, input().split()))
a.sort(reverse=True)
b = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
dp = [0 for _ in range(n + 1)]
INF = 10 ** 9
for i in range(1, n + 1):
    c = [dp[i - b[aj]] for aj in a if i >= b[aj]]
    if len(c) > 0:
        dp[i] = max(c) + 1
    else:
        dp[i] = -INF

x = n
i = 0
ans = ''
while(True):
    for aj in a:
        if x - b[aj] >= 0 and dp[x - b[aj]] == dp[n] - i - 1:
            i += 1
            x -= b[aj]
            ans += str(aj)
            break
    if i == dp[n]:
        break
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n, k = map(int, input().split())
h = list(map(int, input().split()))

dp = [0 for _ in range(n)]
for i in range(1, n):
    hi = h[i]
    x = 2 * 10 ** 9
    for j in range(1, min(k, i) + 1):
        x = min(x, dp[i - j] + abs(hi - h[i - j]))
    dp[i] = x
print(dp[-1])


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

dp = [0 for _ in range(n)]
for i in range(1, n):
    hi = h[i]
    x = 2 * 10 ** 9
    for j in range(1, min(k, i) + 1):
        x = min(x, dp[i - j] + abs(hi - h[i - j]))
    dp[i] = x
print(dp[-1])

Buggy python submission (verdict: Time Limit Exceeded):
n, k = map(int, input().split())
h = list(map(int, input().split()))

dp = [2 * 10 ** 9 for _ in range(n)]
dp[0] = 0
for i in range(1, n):
    hi = h[i]
    for j in range(1, min(k, i) + 1):
        dp[i] = min(dp[i], dp[i - j] + abs(hi - h[i - j]))
print(dp[-1])


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

dp = [0 for _ in range(n)]
for i in range(1, n):
    hi = h[i]
    x = 2 * 10 ** 9
    for j in range(1, min(k, i) + 1):
        x = min(x, dp[i - j] + abs(hi - h[i - j]))
    dp[i] = x
print(dp[-1])
Buggy python submission (verdict: Time Limit Exceeded):
n, w = map(int, input().split())
x = [list(map(int, input().split())) for _ in range(n)]

dp = [[0 for j in range(w + 1)] for i in range(2)]

for i, (wi, vi) in enumerate(x):
    dp_pre = dp[1 - i % 2]
    dp_cur = dp[i % 2]
    for j in range(1, wi):
        dp_cur[j] = dp_pre[j]
    for j in range(wi, w + 1):
        dp_cur[j] = max(dp_pre[j], dp_pre[j - wi] + vi)
print(max(dp_cur))


Fixed submission:
n, w = map(int, input().split())
x = [list(map(int, input().split())) for _ in range(n)]

dp = [[0 for j in range(w + 1)] for i in range(2)]

for i, (wi, vi) in enumerate(x):
    dp_pre = dp[1 - i % 2]
    dp_cur = dp[i % 2]
    for j in range(1, wi):
        dp_cur[j] = dp_pre[j]
    for j in range(wi, w + 1):
        dp_cur[j] = max(dp_pre[j], dp_pre[j - wi] + vi)
print(max(dp_cur))

Buggy python submission (verdict: Time Limit Exceeded):
n, w = map(int, input().split())
x = [list(map(int, input().split())) for _ in range(n)]

dp = [[0 for j in range(w + 1)] for i in range(2)]

for i, (wi, vi) in enumerate(x):
    for j in range(1, wi):
        dp[i % 2][j] = dp[1 - i % 2][j]
    for j in range(wi, w + 1):
        dp[i % 2][j] = max(dp[1 - i % 2][j], dp[1 - i % 2][j - wi] + vi)
print(max(dp[i % 2]))


Fixed submission:
n, w = map(int, input().split())
x = [list(map(int, input().split())) for _ in range(n)]

dp = [[0 for j in range(w + 1)] for i in range(2)]

for i, (wi, vi) in enumerate(x):
    dp_pre = dp[1 - i % 2]
    dp_cur = dp[i % 2]
    for j in range(1, wi):
        dp_cur[j] = dp_pre[j]
    for j in range(wi, w + 1):
        dp_cur[j] = max(dp_pre[j], dp_pre[j - wi] + vi)
print(max(dp_cur))
Buggy python submission (verdict: Time Limit Exceeded):
n, w = map(int, input().split())
x = [list(map(int, input().split())) for _ in range(n)]

dp = [[0 for j in range(w + 1)] for i in range(2)]

for i, (wi, vi) in enumerate(x):
    dp_pre = dp[1 - i % 2]
    dp_cur = dp[i % 2]
    for j in range(1, wi):
        dp_cur[j] = dp_pre[j]
    for j in range(wi, w + 1):
        dp_cur[j] = max(dp_pre[j], dp_pre[j - wi] + vi)
print(max(dp_cur))


Fixed submission:
n, w = map(int, input().split())
x = [list(map(int, input().split())) for _ in range(n)]

v = sum([vi for _, vi in x])
dp = [[2 * 10 ** 9 for j in range(v + 1)] for i in range(2)]
dp[0][0] = 0
dp[1][0] = 0

for i, (wi, vi) in enumerate(x):
    dp_pre = dp[1 - i % 2]
    dp_cur = dp[i % 2]
    for j in range(1, vi):
        dp_cur[j] = dp_pre[j]
    for j in range(vi, v + 1):
        dp_cur[j] = min(dp_pre[j], dp_pre[j - vi] + wi)
ans = 0
for vi, wi in enumerate(dp_cur):
    if wi <= w:
        ans = max(ans, vi)
print(ans)
Buggy python submission (verdict: Runtime Error):
from collections import defaultdict

def rec(v, dp, E):
    if dp[v] != -1:
        return dp[v]
    x = 0
    for w in E[v]:
        x = max(x, rec(w, dp, E) + 1)
    dp[v] = x
    return x

n, m = map(int, input().split())
E = defaultdict(list)
for i in range(m):
    x, y = map(int, input().split())
    E[x - 1].append(y - 1)

dp = [-1 for _ in range(n)]
ans = 0
for i in range(n):
    ans = max(ans, rec(i, dp, E))
print(ans)


Fixed submission:
import sys
from collections import defaultdict

sys.setrecursionlimit(10 ** 5 + 100)

def rec(v, dp, E):
    if dp[v] != -1:
        return dp[v]
    x = 0
    for w in E[v]:
        x = max(x, rec(w, dp, E) + 1)
    dp[v] = x
    return x

n, m = map(int, input().split())
E = defaultdict(list)
for i in range(m):
    x, y = map(int, input().split())
    E[x - 1].append(y - 1)

dp = [-1 for _ in range(n)]
ans = 0
for i in range(n):
    ans = max(ans, rec(i, dp, E))
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
p = list(map(float, input().split()))

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


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

dp = [0 for j in range(n + 1)]
dp[0] = 1
for i in range(n):
    pi = p[i]
    for j in range(i, -1, -1):
        dp[j + 1] = dp[j + 1] * pi + dp[j] * (1 - pi)
    dp[0] *= pi
print(sum(dp[:n // 2 + 1]))
Buggy python submission (verdict: Time Limit Exceeded):
class BIT(object):
    def __init__(self, N, init=0, mod=1):
        self.N = N
        self.bit = [init for _ in range(N)]
        self.mod = mod

    def add(self, k, w):
        x = k
        while x < self.N:
            self.bit[x] += w % self.mod
            self.bit[x] %= self.mod
            x |= x + 1

    def sum(self, k):
        s = 0
        x = k - 1
        while x >= 0:
            s += self.bit[x]
            s %= self.mod
            x = (x & (x + 1)) - 1
        return s

MOD = 10 ** 9 + 7
n, k = map(int, input().split())
a = list(map(int, input().split()))

bit = BIT(k + 1, mod=MOD)
bit.add(0, 1)

for ai in a:
    for i in range(k, 0, -1):
        if ai >= i:
            x = bit.sum(i)
        else:
            x = bit.sum(i) - bit.sum(i - ai)
        bit.add(i, x % MOD)
print(bit.sum(k + 1) - bit.sum(k))


Fixed submission:
MOD = 10 ** 9 + 7
n, k = map(int, input().split())
a = list(map(int, input().split()))

dp = [0 for _ in range(k + 1)]
dp[0] = 1
b = [1 for _ in range(k + 2)]
b[0] = 0

for ai in a:
    for i in range(k, -1, -1):
        dp[i] += (b[i] - b[i - min(ai, i)]) % MOD
        dp[i] %= MOD
    for i in range(1, k + 2):
        b[i] = (b[i - 1] + dp[i - 1]) % MOD
        b[i] %= MOD
print(dp[-1])