Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque, Counter
N, M, K = list(map(int, input().split()))
F = [[0 for _ in range(N)] for _ in range(N)]
B = [[0 for _ in range(N)] for _ in range(N)]
for _ in range(M):
    a, b = list(map(int, input().split()))
    a -= 1
    b -= 1
    F[a][b] = 1
    F[b][a] = 1

for _ in range(K):
    a, b = list(map(int, input().split()))
    a -= 1
    b -= 1
    B[a][b] = 1
    B[b][a] = 1

# まだ探索済みでない頂点からdfs
# どの頂点がどの連結成分に属するかを管理
connect_group = {}

for i in range(N):
    if connect_group.get(i) is not None:
        continue
    stack = deque()
    stack.append(i)
    connect_group[i] = i
    p = -1    
    while len(stack):
        j = stack.pop()
        connect_group[j] = i
        for k, v in enumerate(F[j]):
            if v == 1 and connect_group.get(k) is None:
                stack.append(k)
                connect_group[k] = i
                
ans = []
connect_len = Counter(connect_group.values())
for i in range(N):
    g = connect_group[i]
    l = connect_len[g]
    x = 0
    for j in range(N):
        if i != j:
            if g == connect_group[j]:
                if F[i][j] or B[i][j]:
                    x += 1
    ans.append(str(l - x - 1))

print(' '.join(ans))

Fixed submission:
from collections import deque, Counter
N, M, K = list(map(int, input().split()))
F = [[] for _ in range(N)]
B = [[] for _ in range(N)]

for _ in range(M):
    a, b = list(map(int, input().split()))
    a -= 1
    b -= 1
    F[a].append(b)
    F[b].append(a)

for _ in range(K):
    a, b = list(map(int, input().split()))
    a -= 1
    b -= 1
    B[a].append(b)
    B[b].append(a)

# まだ探索済みでない頂点からdfs
# どの頂点がどの連結成分に属するかを管理
connect_group = {}

for i in range(N):
    if connect_group.get(i) is not None:
        continue
    stack = deque()
    stack.append(i)
    connect_group[i] = i
    p = -1    
    while len(stack):
        j = stack.pop()
        connect_group[j] = i
        for k in F[j]:
            if connect_group.get(k) is None:
                stack.append(k)
                connect_group[k] = i


ans = []
connect_len = Counter(connect_group.values())
for i in range(N):
    g = connect_group[i]
    l = connect_len[g]
    x = 0
    for j in set(F[i]).union(set(B[i])):
        if g == connect_group[j]:
            x += 1
    ans.append(str(l - x - 1))

print(' '.join(ans))
Buggy python submission (verdict: Time Limit Exceeded):
n, k = list(map(int, input().split()))
P = list(map(int, input().split()))

dp = [0] * n
m = {}

def func(x):
    return m.get(x, sum(range(x+1)) / x)
    #return sum(range(x+1)) / x

for i in range(n):
    if i - k >= 0:
        dp[i] = dp[i - 1] - func(P[i - k]) + func(P[i])
    else:        
        dp[i] = sum([func(p) for p in P[:i + 1]])

print(max(dp))

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

dp = [0] * n
m = {}

def func(x):
    return m.get(x, sum(range(x+1)) / x)
    #return sum(range(x+1)) / x

for i in range(n):
    if i - k >= 0:
        dp[i] = dp[i - 1] - func(P[i - k]) + func(P[i])
    else:
        dp[i] += func(P[i]) + dp[i-1]

print(max(dp))

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

dp = [0] * n

def func(x):
    return sum(range(x+1)) / x

for i in range(n):
    if i - k >= 0:
        dp[i] = dp[i - 1] - func(P[i - k]) + func(P[i])
    else:
        dp[i] = sum([func(p) for p in P[:i + 1]])

print(max(dp))

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

dp = [0] * n
m = {}

def func(x):
    return m.get(x, sum(range(x+1)) / x)
    #return sum(range(x+1)) / x

for i in range(n):
    if i - k >= 0:
        dp[i] = dp[i - 1] - func(P[i - k]) + func(P[i])
    else:
        dp[i] += func(P[i]) + dp[i-1]

print(max(dp))
Buggy python submission (verdict: Runtime Error):
import math
H = int(input())
n = math.floor(math.log2(H))
c = 1
for i in range(n):
    c += (2 ** (i+1))
print(c)


Fixed submission:
import math
H = int(input())
n = math.floor(math.log(H, 2))
c = 1
for i in range(n):
    c += (2 ** (i+1))
print(c)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
P = list(map(int, input().split()))
c = 0
for i in range(N):
    if all([P[i] <= p for p in P[:i+1]]):
        c += 1
    #if P[i] >= P[i + 1]:
     #   c += 1
print(c)


Fixed submission:
N = int(input())
P = list(map(int, input().split()))
c = 0
m = N+1
for i in range(N):
    if P[i] <= m:
        c += 1
    m = min(P[i], m)
print(c)
Buggy python submission (verdict: Runtime Error):
import math
N, M = list(map(int, input().split()))
A = list(map(int, input().split()))
A = [a//2 for a in A]

def lcm(a, b):
    return (a*b) // math.gcd(a, b)

k = A[0]
for a in A[1:]:
    k = lcm(a, k)

M = M - (M % k)
b = M % 2
if b == 1:
    print(((M / k)+1)/2)
else:
    print((M / k) / 2)
    

Fixed submission:
from fractions import gcd
import sys
input = sys.stdin.readline

N, M = list(map(int, input().split()))
A = list(map(int, input().split()))
A = [a//2 for a in A]

def lcm(a, b):
    return (a*b) // gcd(a, b)

k = A[0]
for a in A[1:]:
    k = lcm(a, k)

M = M - (M % k)
b = M // k


if b % 2 == 0:
    r = int(b/2)
else:
    r = int((b + 1) / 2)

for a in A[1:]:
    if k // a % 2 == 0:
        r = 0
        break

print(r)

Buggy python submission (verdict: Runtime Error):
import math
N, M = list(map(int, input().split()))
A = list(map(int, input().split()))
A = [a//2 for a in A]

def lcm(a, b):
    return (a*b) // math.gcd(a, b)

k = A[0]
for a in A[1:]:
    k = lcm(a, k)

M = M - (M % k)
b = M % 2
if b == 1:
    print((M / k)+1/2)
else:
    print((M / k) / 2)

Fixed submission:
from fractions import gcd
import sys
input = sys.stdin.readline

N, M = list(map(int, input().split()))
A = list(map(int, input().split()))
A = [a//2 for a in A]

def lcm(a, b):
    return (a*b) // gcd(a, b)

k = A[0]
for a in A[1:]:
    k = lcm(a, k)

M = M - (M % k)
b = M // k


if b % 2 == 0:
    r = int(b/2)
else:
    r = int((b + 1) / 2)

for a in A[1:]:
    if k // a % 2 == 0:
        r = 0
        break

print(r)

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

X = [a / 2 for a in A]
c = 0
for m in range(1, M + 1):
    if [m % a for a in A] == X:
        c += 1
print(c)

Fixed submission:
from fractions import gcd
import sys
input = sys.stdin.readline

N, M = list(map(int, input().split()))
A = list(map(int, input().split()))
A = [a//2 for a in A]

def lcm(a, b):
    return (a*b) // gcd(a, b)

k = A[0]
for a in A[1:]:
    k = lcm(a, k)

M = M - (M % k)
b = M // k


if b % 2 == 0:
    r = int(b/2)
else:
    r = int((b + 1) / 2)

for a in A[1:]:
    if k // a % 2 == 0:
        r = 0
        break

print(r)
Buggy python submission (verdict: Runtime Error):
import numpy as np
from copy import deepcopy
N = int(input())

status = [[] for _ in range(N)]
for i in range(N):
    A = int(input())
    for _ in range(A):
        x, y = list(map(int, input().split()))
        status[i].append((x-1,y))

honest = 0

# bit全探索
for i in range(2 ** N):
    flag = True
    for j in range(N):
        if ((i >> j) & 1) == 1:
            # bitが立っている箇所に対して処理。つまり,人jが正直者だとしたとき、
            # その人の発言と、矛盾していないか判定
            for x, y in status[j]: # 人jの証言            
                if ((i >> x) & 1) != y:
                    flag = False
                    break
    if flag:
        honest = max(honest, bin(i)[2:].count('1'))  # 0bが先頭につくため

print(honest)

Fixed submission:
N = int(input())

status = [[] for _ in range(N)]
for i in range(N):
    A = int(input())
    for _ in range(A):
        x, y = list(map(int, input().split()))
        status[i].append((x-1,y))

honest = 0

# bit全探索
for i in range(2 ** N):
    flag = True
    for j in range(N):
        if ((i >> j) & 1) == 1:
            # bitが立っている箇所に対して処理。つまり,人jが正直者だとしたとき、
            # その人の発言と、矛盾していないか判定
            for x, y in status[j]: # 人jの証言            
                if ((i >> x) & 1) != y:
                    flag = False
                    break
    if flag:
        honest = max(honest, bin(i)[2:].count('1'))  # 0bが先頭につくため

print(honest)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
L = sorted(list(map(int, input().split())))[::-1]

s = 0
for i in range(N-2):
    for j in range(i + 1, N-1):        
        if L[j + 1] > abs(L[i] - L[j]):
            s += N - (j + 1)
            k = N - 1
            while True:
                if L[k] > abs(L[i] - L[j]):
                    break
                else:
                    s -= 1
                    k -= 1
print(s)

Fixed submission:
import bisect
N = int(input())
L = sorted(list(map(int, input().split())))

s = 0
for i in range(N):
    for j in range(i + 1, N):        
        k = bisect.bisect_left(L, L[i] + L[j])
        s += k - j - 1

print(s)

Buggy python submission (verdict: Runtime Error):
s = 0
for i in range(N-2):
    for j in range(i + 1, N-1):        
        if L[j + 1] > abs(L[i] - L[j]):
            s += N - (j + 1)
            k = N - 1
            while True:
                if L[k] > abs(L[i] - L[j]):
                    break
                else:
                    s -= 1
                    k -= 1
print(s)

Fixed submission:
import bisect
N = int(input())
L = sorted(list(map(int, input().split())))

s = 0
for i in range(N):
    for j in range(i + 1, N):        
        k = bisect.bisect_left(L, L[i] + L[j])
        s += k - j - 1

print(s)

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
L = sorted(list(map(int, input().split())))[::-1]

s = 0
for i in range(N):
    for j in range(i+1, N):        
        a = L[i]
        b = L[j]
        for k in range(j + 1, N):
            c = L[k]
            if a < b + c and b < a + c:
                #a - c < b < a + c
                s += 1
print(s)

Fixed submission:
import bisect
N = int(input())
L = sorted(list(map(int, input().split())))

s = 0
for i in range(N):
    for j in range(i + 1, N):        
        k = bisect.bisect_left(L, L[i] + L[j])
        s += k - j - 1

print(s)
Buggy python submission (verdict: Time Limit Exceeded):
from collections import Counter
n = int(input())
S = Counter()
ans = 0
for _ in range(n):
    s = str(sorted(input()))
    if S[s] > 0:
        ans += S[s]
    S[s] += 1

print(ans)

Fixed submission:
from collections import Counter
n = int(input())
S = Counter()
ans = 0
for _ in range(n):
    s = "".join(sorted(input()))
    if S[s] > 0:
        ans += S[s]
    S[s] += 1

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
from collections import Counter
n = int(input())
S = Counter()
ans = 0
for _ in range(n):
    s = str(sorted(list(input())))
    if S[s] > 0:
        ans += S[s]
    S[s] += 1

print(ans)

Fixed submission:
from collections import Counter
n = int(input())
S = Counter()
ans = 0
for _ in range(n):
    s = "".join(sorted(input()))
    if S[s] > 0:
        ans += S[s]
    S[s] += 1

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
from collections import Counter
n = int(input())
S = []
for _ in range(n):
    S.append(Counter(list(input())))

ans = 0
for i in range(n):
    for j in range(n):
        if i < j:
            c_i = S[i]
            c_j = S[j]
            f = 0
            for k_i, v_i in c_i.items():
                if c_j[k_i] != v_i:
                    f = 1
                    break
            if f == 0:
                ans += 1

print(ans)

Fixed submission:
from collections import Counter
n = int(input())
S = Counter()
ans = 0
for _ in range(n):
    s = "".join(sorted(input()))
    if S[s] > 0:
        ans += S[s]
    S[s] += 1

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
from collections import Counter

N = int(input())

c = Counter(list(map(int, input().split())))
D = sorted(list(c.keys()))

x = 0
s = 0
for k in D:
    a = sum([c[d] for d in D if d <= k])
    b = sum([c[d] for d in D if d > k])
    if a == b:
        x = k
    elif a > b and x > 0:
        s = k - x
        break

print(s)

Fixed submission:
from collections import Counter

N = int(input())

c = Counter(list(map(int, input().split())))
D = sorted(list(c.keys()))

x = 0
s = 0
a = 0
b = N
for k in D:
    a += c[k]
    b = N - a
    if a == b:
        x = k
    elif a > b and x > 0:
        s = k - x
        break

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

def lcm(x, y):
    return (x * y) // math.gcd(x, y)

a, b, c, d = list(map(int, input().split()))

_ac = (a-1) // c # a以下のcの倍数の数
_bc = b // c # b以下のcの倍数の数

_ad = (a-1) // d # a以下のdの倍数の数
_bd = b // d # b以下のdの倍数の数

_acd = (a-1) // lcm(c,d) # a以下のcdの倍数の数
_bcd = b // lcm(c,d) # b以下のcdの倍数の数

m = (b-a+1) - ((_bc-_ac) + (_bd-_ad) - (_bcd-_acd))
print(m)

Fixed submission:
from fractions import gcd

def lcm(x, y):
    return (x * y) // gcd(x, y)

a, b, c, d = list(map(int, input().split()))

_ac = (a-1) // c # a以下のcの倍数の数
_bc = b // c # b以下のcの倍数の数

_ad = (a-1) // d # a以下のdの倍数の数
_bd = b // d # b以下のdの倍数の数

_acd = (a-1) // lcm(c,d) # a以下のcdの倍数の数
_bcd = b // lcm(c,d) # b以下のcdの倍数の数

m = (b-a+1) - ((_bc-_ac) + (_bd-_ad) - (_bcd-_acd))
print(m)

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

def lcm(x, y):
    return (x * y) // math.gcd(x, y)

a, b, c, d = list(map(int, input().split()))

_ac = (a-1) // c
_bc = b // c

_ad = (a-1) // d
_bd = b // d

_acd = (a-1) // lcm(c,d)
_bcd = b // lcm(c,d)

m = (b-a+1) - ((_bc-_ac) + (_bd-_ad) - (_bcd-_acd))
print(m)



Fixed submission:
from fractions import gcd

def lcm(x, y):
    return (x * y) // gcd(x, y)

a, b, c, d = list(map(int, input().split()))

_ac = (a-1) // c # a以下のcの倍数の数
_bc = b // c # b以下のcの倍数の数

_ad = (a-1) // d # a以下のdの倍数の数
_bd = b // d # b以下のdの倍数の数

_acd = (a-1) // lcm(c,d) # a以下のcdの倍数の数
_bcd = b // lcm(c,d) # b以下のcdの倍数の数

m = (b-a+1) - ((_bc-_ac) + (_bd-_ad) - (_bcd-_acd))
print(m)

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

def lcm(x, y):
    return (x * y) // math.gcd(x, y)

a, b, c, d = list(map(int, input().split()))

_ac = (a-1) // c # a以下のcの倍数の数
_bc = b // c # b以下のcの倍数の数

_ad = (a-1) // d # a以下のdの倍数の数
_bd = b // d # b以下のdの倍数の数

_acd = (a-1) // lcm(c,d) # a以下のcdの倍数の数
_bcd = b // lcm(c,d) # b以下のcdの倍数の数

m = (b-a+1) - ((_bc-_ac) + (_bd-_ad) - (_bcd-_acd))
print(m)



Fixed submission:
from fractions import gcd

def lcm(x, y):
    return (x * y) // gcd(x, y)

a, b, c, d = list(map(int, input().split()))

_ac = (a-1) // c # a以下のcの倍数の数
_bc = b // c # b以下のcの倍数の数

_ad = (a-1) // d # a以下のdの倍数の数
_bd = b // d # b以下のdの倍数の数

_acd = (a-1) // lcm(c,d) # a以下のcdの倍数の数
_bcd = b // lcm(c,d) # b以下のcdの倍数の数

m = (b-a+1) - ((_bc-_ac) + (_bd-_ad) - (_bcd-_acd))
print(m)
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
T = []
for _ in range(n):
    a, b = list(map(int, input().split()))
    T.append((a, b))
T = sorted(T, key=lambda x: x[1])[::-1]
d = [0] * n
d[0] = T[-1][0]
for i in range(n-1):
    d[i + 1] = d[i] + T[::-1][i + 1][0]
d = d[::-1]

f = 0
for i, (a, b) in enumerate(T):
    if b < d[i]:
        f = 1
        break
if f == 0:
    print('Yes')
else:
    print('No')


Fixed submission:
n = int(input())
T = []
s = 0
for _ in range(n):
    a, b = list(map(int, input().split()))
    T.append((a, b))
    s += a
T = sorted(T, key=lambda x: x[1])[::-1]
f = 0
for i, (a, b) in enumerate(T):
    if b < s:
        f = 1
        break
    s -= a
if f == 0:
    print('Yes')
else:
    print('No')
Buggy python submission (verdict: Time Limit Exceeded):
N, W = map(int, input().split())
w_v = [list(map(int, input().split())) for _ in range(N)]
dp = [[-1 for _ in range(W+1)] for _ in range(N)]

# 1~i-1番目の品物から重さの総和がj以下になるように選んだときの価値を返す
def f(i, j):
    # 終了条件
    if i == N:
        return 0

    if dp[i][j] != -1:
        return dp[i][j]

    w, v = w_v[i]

    # これ以上入らないとき
    if j - w < 0:
        dp[i][j] = f(i+1, j)

    # まだ入るときは両方試す
    else:
        dp[i][j] = max(f(i+1, j), f(i+1, j-w)+v)
    return dp[i][j]

print(f(0, W))


Fixed submission:
N, W = map(int, input().split())
w_v = [list(map(int, input().split())) for _ in range(N)]


# 1~i-1番目の品物から重さの総和がj以下になるように選んだときの価値
dp = [[0 for _ in range(W+1)] for _ in range(N+1)]

for i in range(N):
    w, v = w_v[i]
    for j in range(W+1):
        if j - w >= 0:
            dp[i+1][j] = max(dp[i][j-w]+v, dp[i][j])
        else:
            dp[i+1][j] = dp[i][j]

print(max(dp[N]))

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

def f(i, _w, _v):
    # 終了条件
    if i == N:
        return _v
    w, v = w_v[i]
    # i番目のものは入らないとき
    if _w + w > W:
        return f(i+1, _w, _v)

    # まだ入るときは両方試す
    else:
        return max(f(i+1, _w, _v), f(i+1, _w+w, _v+v))

print(f(0, 0, 0))


Fixed submission:
N, W = map(int, input().split())
w_v = [list(map(int, input().split())) for _ in range(N)]


# 1~i-1番目の品物から重さの総和がj以下になるように選んだときの価値
dp = [[0 for _ in range(W+1)] for _ in range(N+1)]

for i in range(N):
    w, v = w_v[i]
    for j in range(W+1):
        if j - w >= 0:
            dp[i+1][j] = max(dp[i][j-w]+v, dp[i][j])
        else:
            dp[i+1][j] = dp[i][j]

print(max(dp[N]))
Buggy python submission (verdict: Time Limit Exceeded):
N, W = map(int, input().split())
w_v = [list(map(int, input().split())) for _ in range(N)]
 
 
# 1~i-1番目の品物から重さの総和がj以下になるように選んだときの価値
dp = [[0 for _ in range(W+1)] for _ in range(N+1)]
 
for i in range(N):
    w, v = w_v[i]
    for j in range(W+1):
        if j - w >= 0:
            dp[i+1][j] = max(dp[i][j-w]+v, dp[i][j])
        else:
            dp[i+1][j] = dp[i][j]
 
print(max(dp[N]))
 
 

Fixed submission:
N, W = map(int, input().split())
w_v = [list(map(int, input().split())) for _ in range(N)]

V = max(w_v, key=lambda x: x[1])[1] * N
# 1~i-1番目の品物から価値の総和がj以下になるように選んだときの重さ
dp = [[float('inf') for _ in range(V+1)] for _ in range(N+1)]
dp[0][0] = 0

for i in range(N):
    w, v = w_v[i]
    for j in range(V+1):
        if j - v >= 0:
            dp[i+1][j] = min(dp[i][j-v]+w, dp[i][j])
        else:
            #dp[i+1][j] = min(dp[i][j], dp[i+1][j])
            dp[i+1][j] = dp[i][j]

r = 0
for v in range(V+1):
    if dp[N][v] <= W:
        r = v
print(r)
Buggy python submission (verdict: Runtime Error):
n, m = map(int, input().split())

edges = [[] for _ in range(n+1)]
for _ in range(m):
    x, y = map(int, input().split())
    edges[x].append(y)

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

def longest_path(u):
    if dp[u] != -1:
        return dp[u]
    d = 0
    for v in edges[u]:
        d = max(d, 1+longest_path(v))
    dp[u] = d
    return d

for u in range(1, n+1):
    longest_path(u)

print(max(dp))


Fixed submission:
import sys
sys.setrecursionlimit(10**5)

n, m = map(int, input().split())

edges = [[] for _ in range(n+1)]
for _ in range(m):
    x, y = map(int, input().split())
    edges[x].append(y)

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

def longest_path(u):
    if dp[u] != -1:
        return dp[u]
    d = 0
    for v in edges[u]:
        d = max(d, 1+longest_path(v))
    dp[u] = d
    return d

for u in range(1, n+1):
    longest_path(u)

print(max(dp))

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

edges = [[] for _ in range(n+1)]
for _ in range(m):
    x, y = map(int, input().split())
    edges[x].append(y)

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

def longest_path(u):
    if dp[u] != -1:
        return dp[u]
    d = 0
    for v in edges[u]:
        d = max(d, 1+longest_path(v))
    dp[u] = d
    return d

for u in range(n+1):
    longest_path(u)

print(max(dp))


Fixed submission:
import sys
sys.setrecursionlimit(10**5)

n, m = map(int, input().split())

edges = [[] for _ in range(n+1)]
for _ in range(m):
    x, y = map(int, input().split())
    edges[x].append(y)

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

def longest_path(u):
    if dp[u] != -1:
        return dp[u]
    d = 0
    for v in edges[u]:
        d = max(d, 1+longest_path(v))
    dp[u] = d
    return d

for u in range(1, n+1):
    longest_path(u)

print(max(dp))

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

edges = [[0 for _ in range(n+1)] for _ in range(n+1)]
for _ in range(m):
    x, y = map(int, input().split())
    edges[x][y] = 1

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

def longest_path(u):
    if dp[u] != -1:
        return dp[u]
    d = 0
    for i in range(1, n+1):
        if edges[u][i]:
            d = max(d, 1+longest_path(i))
    dp[u] = d
    return d

for u in range(n+1):
    longest_path(u)

print(max(dp))


Fixed submission:
import sys
sys.setrecursionlimit(10**5)

n, m = map(int, input().split())

edges = [[] for _ in range(n+1)]
for _ in range(m):
    x, y = map(int, input().split())
    edges[x].append(y)

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

def longest_path(u):
    if dp[u] != -1:
        return dp[u]
    d = 0
    for v in edges[u]:
        d = max(d, 1+longest_path(v))
    dp[u] = d
    return d

for u in range(1, n+1):
    longest_path(u)

print(max(dp))
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
A = list(map(int, input().split()))

# dp[i][j][k]: 寿司が残り1個の皿がi枚, 残り2個の皿がj枚, 残り3個の皿がk枚から寿司をすべてなくす操作回数の期待値
dp = [[[0 for _ in range(n+1)] for _ in range(n+1)] for _ in range(n+1)]

one = A.count(1)
two = A.count(2)
three = A.count(3)

# i, j, kを全通り回す
for k in range(three + 1):
    # 3個の皿がk個のとき
    for j in range(two + three - k + 1):
        # 2枚の皿は
        # 初期のtwo
        # 3個の皿がk枚のとき、three-k枚が2枚になっている
        for i in range(one + (two + (three - k) - j) + 1):
            # 1枚の皿は
            # 初期のone
            # 3枚の皿がk枚、2枚の皿がj枚のとき、two+three-k-j枚が1枚になっている
            if i == 0 and j == 0 and k == 0:
                continue
            tmp = n
            if i > 0:
                tmp += i * dp[i - 1][j][k]
            if j > 0:
                tmp += j * dp[i + 1][j - 1][k]
            if k > 0:
                tmp += k * dp[i][j + 1][k - 1]
            
            dp[i][j][k] = tmp / (i + j + k)

print(dp[i][j][k])

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

# dp[i][j][k]: 寿司が残り1個の皿がi枚, 残り2個の皿がj枚, 残り3個の皿がk枚から寿司をすべてなくす操作回数の期待値
dp = [[[0.0 for _ in range(n+1)] for _ in range(n+1)] for _ in range(n+1)]

one = A.count(1)
two = A.count(2)
three = A.count(3)

# i, j, kを全通り回す
for k in range(three + 1):
    # 3個の皿がk個のとき
    for j in range(two + three - k + 1):
        # 2枚の皿は
        # 初期のtwo
        # 3個の皿がk枚のとき、three-k枚が2枚になっている
        for i in range(one + two + three - k - j + 1):
            # 1枚の皿は
            # 初期のone
            # 3枚の皿がk枚、2枚の皿がj枚のとき、two+three-k-j枚が1枚になっている
            if i == 0 and j == 0 and k == 0:
                continue
            tmp = 1.0*n
            if i > 0:
                tmp += i * dp[i - 1][j][k]
            if j > 0:
                tmp += j * dp[i + 1][j - 1][k]
            if k > 0:
                tmp += k * dp[i][j + 1][k - 1]
            
            dp[i][j][k] = tmp / (i + j + k)

print(dp[one][two][three])
Buggy python submission (verdict: Runtime Error):
N, K = list(map(int, input().split()))
A = list(map(int, input().split()))

# dp[i]: 残りがi個の状態で先手が勝つかどうか
dp = [-1 for _ in range(K+1)]

# dp[i] = 0: 残りi個で先手が負ける
# dp[i] = 1: 残りi個で先手が勝つ
# dp[i] = -1: 残りi個でも不明

for i in range(K + 1):
    # 遷移先: i-aで、そのとき手番は後手
    # どのi-aも1 = 後手がかならず勝つ = 負け
    # 1つでも0がある = 1つでも勝ち筋がある = (その手を打てば)勝ち
    # 
    # どのi-aにも遷移できない = 打てない = 負け
    if all([i - a < 0 for a in A]):
        dp[i] = 0
    else:
        if all([dp[i - a] == 1 for a in A]):
            dp[i] = 0
        elif any([dp[i - a] == 0 for a in A]):
            dp[i] = 1
        else:
            dp[i] |= int(not dp[i-a])

if dp[K]:
    print('First')
else:
    print('Second')

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

# dp[i]: 残りがi個の状態で先手が勝つかどうか
dp = [0 for _ in range(K+1)]

# dp[i] = 0: 残りi個で先手が負ける
# dp[i] = 1: 残りi個で先手が勝つ
# dp[i] = -1: 残りi個でも不明
  
for i in range(K + 1):
    # 遷移先: i-aで、そのとき手番は後手
    # どのi-aも1 = 後手がかならず勝つ = 負け
    # 1つでも0がある = 1つでも勝ち筋がある = (その手を打てば)勝ち
    # どのi-aにも遷移できない = 打てない = 負け
    for a in A:
        # 遷移先が存在し、かつそれが勝ち筋
        if i - a >= 0 and not dp[i - a]:
            dp[i] = 1
            break

if dp[K]:
    print('First')
else:
    print('Second')