Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
N, K = map(int, input().split())
A = sorted(list(map(int, input().split())))
F = tuple(map(int, input().split()))


def can_eat(t):
    F_time = sorted([t // f for f in F])
    training = 0
    for i in range(N):
        training += max(0, A[i] - F_time[i])
    return training <= K


# bisect
l, r = -1, 10 ** 12
while r - l > 1:
    m = (r + l) // 2
    if can_eat(m):
        r = m
    else:
        l = m
print(r)


Fixed submission:
import sys

input = sys.stdin.readline

N, K = map(int, input().split())
A = sorted(list(map(int, input().split())))
F = tuple(map(int, input().split()))


def can_eat(t):
    F_time = sorted([t // f for f in F])
    training = 0
    for i in range(N):
        training += max(0, A[i] - F_time[i])
    return training <= K


# bisect
l, r = -1, 10 ** 12
while r - l > 1:
    m = (r + l) // 2
    if can_eat(m):
        r = m
    else:
        l = m
print(r)
Buggy python submission (verdict: Time Limit Exceeded):
int1 = lambda x: int(x) - 1

N, M = map(int, input().split())
edges = [tuple(map(int1, input().split())) for _ in range(M)]
G = [set() for _ in range(N)]
for s, t in edges:
    G[s].add(t)


def E(dp, i):
    return sum(dp[x] for x in G[i]) / len(G[i]) + 1


dp0 = [0] * N
for i in range(N - 2, -1, -1):
    dp0[i] = E(dp0, i)

ans = dp0[0]
for s, t in edges:
    if len(G[s]) == 1:
        continue

    G[s].remove(t)
    dp = dp0.copy()
    for i in range(s, -1, -1):
        dp[i] = E(dp, i)
    ans = min(ans, dp[0])
    G[s].add(t)
print(ans)

Fixed submission:
int1 = lambda x: int(x) - 1

N, M = map(int, input().split())
edges = [tuple(map(int1, input().split())) for _ in range(M)]
G = [set() for _ in range(N)]
for s, t in edges:
    G[s].add(t)


def E(dp, i):
    return sum(dp[x] for x in G[i]) / len(G[i]) + 1


dp0 = [0] * N
for i in range(N - 2, -1, -1):
    dp0[i] = E(dp0, i)

ans = dp0[0]
for i in range(N - 1):
    if len(G[i]) == 1:
        continue

    maxE = 0
    maxE_ind = None
    for x in G[i]:
        if dp0[x] > maxE:
            maxE_ind = x
            maxE = dp0[x]

    dp = dp0.copy()
    G[i].remove(maxE_ind)
    for j in range(i, -1, -1):
        dp[j] = E(dp, j)
    ans = min(ans, dp[0])
    G[i].add(maxE_ind)

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

table = [float('inf')] * 2 ** N
table[0] = 0
for m in range(M):
    a, _ = map(int, input().split())
    c = sum(2 ** (i - 1) for i in map(int, input().split()))
    for x in range(2 ** N):
        an = x | c
        table[an] = min(table[an], table[x] + a)
ans = table[2 ** N - 1]

print(ans if ans != float('inf') else -1)


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

p2 = 2 ** N
table = [10 ** 9] * p2
table[0] = 0
for m in range(M):
    a, _ = map(int, input().split())
    c = sum(2 ** (i - 1) for i in map(int, input().split()))
    for x in range(p2):
        an = x | c
        table[an] = min(table[an], table[x] + a)
ans = table[p2 - 1]
 
print(ans if ans != 10 ** 9 else -1)

Buggy python submission (verdict: Time Limit Exceeded):
N, M = map(int, input().split())
A, C = [], []
for _ in range(M):
    a, _ = map(int, input().split())
    A.append(a)
    C.append(sum(2 ** (i - 1) for i in map(int, input().split())))

table = [float('inf')] * 2 ** N
table[0] = 0
for m in range(M):
    for x in range(2 ** N):
        an = x | C[m]
        table[an] = min(table[an], table[x] + A[m])
ans = table[2 ** N - 1]

print(ans if ans != float('inf') else -1)


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

p2 = 2 ** N
table = [10 ** 9] * p2
table[0] = 0
for m in range(M):
    a, _ = map(int, input().split())
    c = sum(2 ** (i - 1) for i in map(int, input().split()))
    for x in range(p2):
        an = x | c
        table[an] = min(table[an], table[x] + a)
ans = table[p2 - 1]
 
print(ans if ans != 10 ** 9 else -1)

Buggy python submission (verdict: Time Limit Exceeded):
N, M = map(int, input().split())
A, C = [], []
for _ in range(M):
    a, _ = map(int, input().split())
    A.append(a)
    C.append(sum(2 ** (i - 1) for i in map(int, input().split())))

table = [float('inf')] * 2 ** N
table[0] = 0
for m in range(M):
    for x in range(2 ** N):
        an = x | C[m]
        table[an] = min(table[an], table[an], table[x] + A[m])
ans = table[2 ** N - 1]

print(ans if ans != float('inf') else -1)


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

p2 = 2 ** N
table = [10 ** 9] * p2
table[0] = 0
for m in range(M):
    a, _ = map(int, input().split())
    c = sum(2 ** (i - 1) for i in map(int, input().split()))
    for x in range(p2):
        an = x | c
        table[an] = min(table[an], table[x] + a)
ans = table[p2 - 1]
 
print(ans if ans != 10 ** 9 else -1)
Buggy python submission (verdict: Time Limit Exceeded):
N,K,Q=map(int, input().split())
A=[]
for _ in range(Q):
    A.append(int(input())-1)

for i in range(N):
    if K-Q+A.count(i)>0:
        print("Yes")
    else:
        print("No")

Fixed submission:
N,K,Q=map(int, input().split())
S=[0]*N
for _ in range(Q):
    S[int(input())-1]+=1

for i in range(N):
    if K-Q+S[i]>0:
        print("Yes")
    else:
        print("No")
Buggy python submission (verdict: Time Limit Exceeded):
N, M = map(int, input().split())
Am = list(map(int, input().split()))
A = sorted(Am, reverse=True)
A.append(0)
for m in range(M):
    a = int(A[0] / 2)
    n = 0
    while A[n + 1] > a and n < N - 1:
        n += 1
    del A[0]
    A.insert(n,a)
print(sum(A))

Fixed submission:
import heapq

N, M = map(int, input().split())
A = list(map(int, input().split()))
Am=[-a for a in A]
heapq.heapify(Am)
for m in range(M):
    a = int(heapq.heappop(Am) / 2)
    heapq.heappush(Am, a)
print(-sum(Am))

Buggy python submission (verdict: Time Limit Exceeded):
N, M = map(int, input().split())
Am = list(map(int, input().split()))
A = sorted(Am, reverse=True)
A.append(0)
for m in range(M):
    a = int(A[0] / 2)
    n = 0
    while A[n + 1] > a and n < N - 1:
        A[n] = A[n + 1]
        n += 1
    A[n] = a
print(sum(A))


Fixed submission:
import heapq

N, M = map(int, input().split())
A = list(map(int, input().split()))
Am=[-a for a in A]
heapq.heapify(Am)
for m in range(M):
    a = int(heapq.heappop(Am) / 2)
    heapq.heappush(Am, a)
print(-sum(Am))
Buggy python submission (verdict: Time Limit Exceeded):
import networkx as nx

int1 = lambda x: int(x) - 1

N, Q = map(int, input().split())
G = nx.Graph()
G.add_nodes_from(range(N))
G.add_edges_from([tuple(map(int1, input().split())) for _ in range(N - 1)])

lst = [0] * N
for _ in range(Q):
    p, x = map(int, input().split())
    lst[p - 1] += x

for parent, child in nx.dfs_edges(G, 0):
    lst[child] += lst[parent]

print(*lst)


Fixed submission:
from collections import deque

int1 = lambda x: int(x) - 1

N, Q = map(int, input().split())
T = [[] for _ in range(N)]
for _ in range(N - 1):
    a, b = map(int1, input().split())
    T[a].append(b)
    T[b].append(a)

lst = [0] * N
for _ in range(Q):
    p, x = map(int, input().split())
    lst[p - 1] += x

d = deque([0])
visited = set()
while d:
    v = d.pop()
    visited.add(v)
    for x in T[v]:
        if x not in visited:
            lst[x] += lst[v]
            d.append(x)
print(*lst)
Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np

S = input()
MOD = 10 ** 9 + 7

dp = np.zeros(13, dtype=int)
dp[0] = 1

for s in S:
    # 4 == pow(10, -1, 13)
    dp = dp[np.arange(0, 52, 4) % 13]
    if s == '?':
        new_dp = np.zeros(13, dtype=int)
        for i in range(13):
            new_dp[np.arange(i, i + 10) % 13] += dp[i]
            new_dp %= MOD
        dp = new_dp
    else:
        dp = np.roll(dp, int(s))
print(dp[5])


Fixed submission:
import numpy as np
from numba import njit, i8

S = input()
MOD = 10 ** 9 + 7

dp = np.zeros(13, dtype=int)
dp[0] = 1


@njit(cache=True)
def q_mark(dp):
    new_dp = np.zeros(13, dtype=i8)
    for i in range(13):
        new_dp[np.arange(i, i + 10) % 13] += dp[i]
        new_dp %= MOD
    return new_dp


for s in S:
    # 4 == pow(10, -1, 13)
    dp = dp[np.arange(0, 52, 4) % 13]
    if s == '?':
        dp = q_mark(dp)
    else:
        dp = np.roll(dp, int(s))
print(dp[5])
Buggy python submission (verdict: Runtime Error):
import bisect

N = int(input())
H = []
min_lst = 10 ** 9
for _ in range(N):
    a = int(input())
    if min_lst >= a:
        min_lst = a
        H.append(-a)
    else:
        H[bisect.bisect_left(H, -a)] = -a
print(len(H))


Fixed submission:
import bisect

N = int(input())
H = []
for _ in range(N):
    a = int(input())
    ind = bisect.bisect_right(H, -a)
    if ind == len(H):
        H.append(-a)
    else:
        H[ind] = -a
print(len(H))
Buggy python submission (verdict: Runtime Error):
import numpy as np

N = int(input())
A = np.matrix([int(x) for x in input().split()], dtype='int64')
Pm = np.matrix([[1, -1], [-1, 1]], dtype='int64')
P = np.tile(Pm, ((N + 1) // 2, (N + 1) // 2))[:-1, :-1]
P = -np.triu(P) + np.tril(P) + np.eye(N)
print(*np.array(A * P).flatten().astype(np.int64).tolist())


Fixed submission:
N = int(input())
A = list(map(int, input().split()))
ans = [sum((-1) ** i * A[i] for i in range(N))]
for i in range(N - 1):
    ans.append(2 * A[i] - ans[i])
print(*ans)
Buggy python submission (verdict: Runtime Error):
S = input()
X=S[0]
i=1
while i<=4:
    if S[i]!=X:
        Y=S[i]
        break
    i+=1
if S.count(X)!=2 or S.count(Y)!=2:
    print("No")
else:
    print("Yes")

Fixed submission:
S = input()
X=S[0]
i=1
while i<=3:
    if S[i]!=X:
        Y=S[i]
        break
    i+=1
if S.count(X)!=2 or S.count(Y)!=2:
    print("No")
else:
    print("Yes")
Buggy python submission (verdict: Runtime Error):
import math
A,B,C,D = map(int, input().split())

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

ac=int(A/C)
bc=int(B/C)
ad=int(A/D)
bd=int(B/D)
acd=int(A/lcm(C,D))
bcd=int(B/lcm(C,D))

if A%C==0:
    c_div=bc-ac+1
else:
    c_div = bc - ac
if B%C==0:
    d_div=bd-ad+1
else:
    d_div = bd - ad
if B%lcm(C,D)==0:
    cd_div=bcd-acd+1
else:
    cd_div = bcd - acd

print(B-A+1-c_div-d_div+cd_div)

Fixed submission:
from fractions import gcd

A, B, C, D = map(int, input().split())


def division(x, p, q):
    return x - x // p - x // q + x // (p * q // gcd(p, q))


print(division(B, C, D) - division(A - 1, C, D))
Buggy python submission (verdict: Runtime Error):
import itertools
from collections import defaultdict

N = int(input())
balls = sorted([tuple(map(int, input().split())) for _ in range(N)])

d = defaultdict(int)
for i, j in itertools.combinations(range(N), 2):
    d[(balls[j][0] - balls[i][0], balls[j][1] - balls[i][1])] += 1
print(N - max(d.values()))


Fixed submission:
import itertools
from collections import defaultdict
from sys import exit

N = int(input())
balls = sorted([tuple(map(int, input().split())) for _ in range(N)])

if N == 1:
    print(1)
    exit()

d = defaultdict(int)
for i, j in itertools.combinations(range(N), 2):
    d[(balls[j][0] - balls[i][0], balls[j][1] - balls[i][1])] += 1
print(N - max(d.values()))
Buggy python submission (verdict: Runtime Error):
N, M = map(int, input().split())
A = []
for _ in range(M):
    A.append(int(input()))

case = [0] * (N + 1)
case[0] = 1
if not 1 in A:
    case[1] = 1
for x in range(2, N + 1):
    if x in A:
        case[x] = 0
    elif x - 1 in A:
        case[x] = case[x - 2]
    else:
        case[x] = case[x - 1] + case[x - 2]

print(case[N] % 1000000007)

Fixed submission:
P,Q,R=map(int, input().split())
print(min(P+Q,P+R,Q+R))
Buggy python submission (verdict: Runtime Error):
from sys import exit

N, M = map(int, input().split())
A = list(map(int, input().split()))
BC = []
for _ in range(M):
    BC.append(tuple(map(int, input().split())))
BC.sort(key=lambda x: -x[1])
A.sort()

i = 0
for b, c in BC:
    for x in range(b):
        if A[i] < c:
            A[i] = c
            i += 1
        else:
            print(sum(A))
            exit()
print(sum(A))

Fixed submission:
from sys import exit

N, M = map(int, input().split())
A = list(map(int, input().split()))
BC = []
for _ in range(M):
    BC.append(tuple(map(int, input().split())))
BC.sort(key=lambda x: -x[1])
A.sort()

i = 0
for b, c in BC:
    for x in range(b):
        if i < N and A[i] < c:
            A[i] = c
            i += 1
        else:
            print(sum(A))
            exit()
print(sum(A))

Buggy python submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(3000)

N,M= map(int, input().split())
A=sorted(map(int, input().split()))

D=[[0 for i in range(2)] for j in range(M)]
for x in range(M):
    D[x][0],D[x][1]= map(int, input().split())

D=sorted(D, key=lambda x : x[1],reverse=True)
num=0
for y in range(M): #どの要素を代入するか
    for z in range(D[y][0]): #どこに要素を代入するか
        if A[z+num]>=D[y][1]:
            break
        else:
            A[z+num]=D[y][1]
    else:
        num += D[y][0]
        continue
    break
print(A)
print(sum(A))

Fixed submission:
from sys import exit

N, M = map(int, input().split())
A = list(map(int, input().split()))
BC = []
for _ in range(M):
    BC.append(tuple(map(int, input().split())))
BC.sort(key=lambda x: -x[1])
A.sort()

i = 0
for b, c in BC:
    for x in range(b):
        if i < N and A[i] < c:
            A[i] = c
            i += 1
        else:
            print(sum(A))
            exit()
print(sum(A))

Buggy python submission (verdict: Runtime Error):
N,M= map(int, input().split())
A=sorted(map(int, input().split()))

D=[[0 for i in range(2)] for j in range(M)]
for x in range(M):
    D[x][0],D[x][1]= map(int, input().split())

D=sorted(D, key=lambda x : x[1],reverse=True)

num=0
for y in range(M):
    for z in range(D[y][0]):
        if A[z+num]>=D[y][1]:
            break
        else:
            A[z+num]=D[y][1]
    else:
        num += D[y][0]
        continue
    break
print(sum(A))

Fixed submission:
from sys import exit

N, M = map(int, input().split())
A = list(map(int, input().split()))
BC = []
for _ in range(M):
    BC.append(tuple(map(int, input().split())))
BC.sort(key=lambda x: -x[1])
A.sort()

i = 0
for b, c in BC:
    for x in range(b):
        if i < N and A[i] < c:
            A[i] = c
            i += 1
        else:
            print(sum(A))
            exit()
print(sum(A))
Buggy python submission (verdict: Time Limit Exceeded):
from scipy.sparse import lil_matrix
from scipy.sparse.csgraph import connected_components

N, M = map(int, input().split())
matr = lil_matrix((N, N))

for _ in range(M):
    x, y, z = map(int, input().split())
    matr[x - 1, y - 1] = matr[y - 1, x - 1] = 1

matr = matr.tocsr()
print(connected_components(matr, return_labels=False))


Fixed submission:
import numpy as np
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import connected_components

N, M = map(int, input().split())
edge = np.array([input().split() for _ in range(M)], dtype=np.int64).T

matr = csr_matrix(([1 for _ in range(M)], (edge[:2] - 1)), (N, N))
print(connected_components(matr, return_labels=False))
Buggy python submission (verdict: Time Limit Exceeded):
R,G,B,N= map(int, input().split())
answer=0

for r in range(3001):
    for g in range(3001):
        for b in range(3001):
            if R * r + G * g + B * b == N:
                answer += 1
                break
            elif R * r + G * g + B * b > N:
                break
        if R * r + G * g> N:
            break
    if R*r>N:
        break
print(answer)

Fixed submission:
R, G, B, N = map(int, input().split())
ans = 0
for r in range(3001):
    for g in range(3001):
        Bb = N - R * r - G * g
        if Bb >= 0 and Bb % B == 0:
            ans += 1
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N, K = map(int, input().split())
H = tuple(map(int, input().split()))

table = [0] * N
for i in range(1, N):
    table[i] = min(abs(H[i] - H[j]) + table[j] for j in range(max(0, i - K), i))

print(table[N-1])

Fixed submission:
import numpy as np

N, K = map(int, input().split())
H = np.array(list(map(int, input().split())) + [0] * K, dtype=np.int64)

table = np.full(N + K, 10 ** 10, dtype=np.int64)
table[0] = 0

for i in range(1, N):
    table[i:i + K] = np.minimum(table[i:i + K], np.abs(H[i:i + K] - H[i - 1]) + table[i - 1])

print(table[N - 1])
Buggy python submission (verdict: Time Limit Exceeded):
N, W = map(int, input().split())
goods = []
for _ in range(N):
    goods.append(tuple(map(int, input().split())))

table = [[0] * (W + 1) for _ in range(N + 1)]
for n in range(N):
    for w in range(W + 1):
        addn = table[n][w - goods[n][0]] + goods[n][1] if w - goods[n][0] >= 0 else 0
        table[n + 1][w] = max(table[n][w], addn)
print(table[N][W])


Fixed submission:
import numpy as np

N, W = map(int, input().split())
goods = [tuple(map(int, input().split())) for _ in range(N)]

table = np.zeros((N + 1, W + 1), dtype=np.int64)
for n in range(N):
    tmp = np.zeros(W + 1, dtype=np.int64)
    tmp[goods[n][0]:] = table[n][:W + 1 - goods[n][0]] + goods[n][1]
    table[n + 1] = np.maximum(table[n], tmp)
print(table[N][W])
Buggy python submission (verdict: Time Limit Exceeded):
N, W = map(int, input().split())
goods = [tuple(map(int, input().split())) for _ in range(N)]
Mv = 10 ** 5

table = [[float('inf')] * (Mv + 1) for _ in range(N + 1)]
table[0][0] = 0
for n in range(N):
    for v in range(Mv + 1):
        addn = table[n][v - goods[n][1]] + goods[n][0] if v >= goods[n][1] else float('inf')
        table[n + 1][v] = min(table[n][v], addn)
ans = 0
for i in range(Mv):
    if table[N][i] <= W:
        ans = max(ans, i)
print(ans)


Fixed submission:
import numpy as np

N, W = map(int, input().split())
goods = [tuple(map(int, input().split())) for _ in range(N)]
Mv = 10 ** 5
Mw = 10 ** 11

table = np.full((N + 1, Mv + 1), Mw, dtype=np.int64)
table[0][0] = 0
for n in range(N):
    tmp = np.full(Mv + 1, Mw, dtype=np.int64)
    tmp[goods[n][1]:] = table[n][:Mv + 1 - goods[n][1]] + goods[n][0]
    table[n + 1] = np.minimum(table[n], tmp)

print(np.max(np.where(table[N] <= W, table[N], 0).nonzero()))
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
P = tuple(map(float, input().split()))

dp = [[0 for _ in range(N + 1)] for __ in range(N + 1)]
dp[0][0] = 1
for i in range(N):
    for j in range(N):
        dp[i + 1][j + 1] += dp[i][j] * P[i]
        dp[i + 1][j] += dp[i][j] * (1 - P[i])
print(sum(dp[N][(N + 1) // 2:]))


Fixed submission:
N = int(input())
P = tuple(map(float, input().split()))

dp = [[0 for _ in range(N + 1)] for __ in range(N + 1)]
dp[0][0] = 1
for i in range(N):
    for j in range(N):
        dp[i + 1][j + 1] += dp[i][j] * P[i]
        dp[i + 1][j] += dp[i][j] * (1 - P[i])
print(sum(dp[N][(N + 1) // 2:]))
Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np
from collections import Counter

N = int(input())
A = Counter(map(int, input().split()))
S = (None, A[3] + A[2] + A[1], A[3] + A[2], A[3])

dp = np.zeros((S[1] + 1, S[2] + 1, S[3] + 1), dtype=float)
for l in range(1, S[1] + 1):
    for m in range(S[2] + 1):
        if l < m:
            break
        mk = min(m + 1, S[3] + 1)
        dp[l][m][:mk] = (dp[l - 1][m][:mk] * (l - m) + dp[l][m - 1][:mk] * (m - np.arange(mk)) + N) / l

        matr = np.tile(np.arange(mk) / l, (mk, 1))
        matr[np.tri(mk, dtype=bool)] = 1
        matr = np.multiply.accumulate(matr, axis=1)
        matr[np.tri(mk, k=-1, dtype=bool)] = 0
        np.asmatrix(matr)

        dp[l][m][:mk] = np.dot(dp[l][m][:mk], matr)
print(dp[S[1]][S[2]][S[3]])


Fixed submission:
from collections import Counter

N = int(input())
A = Counter(map(int, input().split()))
S = [None, A[3] + A[2] + A[1], A[3] + A[2], A[3]]

dp = [[[0] * (S[3] + 1) for _ in range(S[2] + 1)] for __ in range(S[1] + 1)]

for l in range(1, S[1] + 1):
    for m in range(S[2] + 1):
        if l < m:
            break
        for k in range(S[3] + 1):
            if m < k:
                break
            dp[l][m][k] = (dp[l - 1][m][k] * (l - m) + dp[l][m - 1][k] * (m - k) + dp[l][m][k - 1] * k + N) / l
print(dp[S[1]][S[2]][S[3]])

Buggy python submission (verdict: Runtime Error):
import numpy as np
from collections import Counter

N = int(input())
A = Counter(map(int, input().split()))
S = (None, A[3] + A[2] + A[1], A[3] + A[2], A[3])

dp = np.zeros((S[1] + 1, S[2] + 1, S[3] + 1), dtype=float)
for l in range(1, S[1] + 1):
    for m in range(S[2] + 1):
        if l < m:
            break
        mk = min(m + 1, S[3] + 1)
        dp[l][m][:mk] = (dp[l - 1][m][:mk] * (l - m) + dp[l][m - 1][:mk] * (m - np.arange(mk)) + N) / l

        matr = np.tile(np.arange(mk) / l, (mk, 1))
        matr[np.tri(mk, dtype=bool)] = 1
        matr = np.multiply.accumulate(matr, axis=1)
        matr[np.tri(mk, k=-1, dtype=bool)] = 0

        dp[l][m][:mk] = dp[l][m][:mk] @ matr
print(dp[S[1]][S[2]][S[3]])


Fixed submission:
from collections import Counter

N = int(input())
A = Counter(map(int, input().split()))
S = [None, A[3] + A[2] + A[1], A[3] + A[2], A[3]]

dp = [[[0] * (S[3] + 1) for _ in range(S[2] + 1)] for __ in range(S[1] + 1)]

for l in range(1, S[1] + 1):
    for m in range(S[2] + 1):
        if l < m:
            break
        for k in range(S[3] + 1):
            if m < k:
                break
            dp[l][m][k] = (dp[l - 1][m][k] * (l - m) + dp[l][m - 1][k] * (m - k) + dp[l][m][k - 1] * k + N) / l
print(dp[S[1]][S[2]][S[3]])
Buggy python submission (verdict: Time Limit Exceeded):
import itertools

N, K = map(int, input().split())
A = tuple(map(int, input().split()))

MOD = 10 ** 9 + 7

dp = [[0] * (K + 1) for _ in range(N + 1)]
dp[0][0] = 1
for i in range(1, N + 1):
    S = [0] + list(itertools.accumulate(dp[i - 1]))
    for j in range(K + 1):
        dp[i][j] = (S[j + 1] - S[max(0, j - A[i - 1])]) % MOD
print(dp[N][K])


Fixed submission:
import itertools

N, K = map(int, input().split())
A = tuple(map(int, input().split()))

MOD = 10 ** 9 + 7

dp = [[0] * (K + 1) for _ in range(N + 1)]
dp[0][0] = 1
for i in range(1, N + 1):
    S = [0] + list(itertools.accumulate(dp[i - 1]))
    for j in range(K + 1):
        dp[i][j] = (S[j + 1] - S[max(0, j - A[i - 1])]) % MOD
print(dp[N][K])
Buggy python submission (verdict: Time Limit Exceeded):
import itertools

N = int(input())
A = tuple(map(int, input().split()))
S = [0] + list(itertools.accumulate(A))

dp = [[0] * (N + 1) for _ in range(N + 1)]
for length in range(2, N + 1):
    for l in range(N - length + 1):
        r = length + l
        dp[l][r] = min(dp[l][m] + dp[m][r] for m in range(l + 1, r)) + S[r] - S[l]
print(dp[0][N])


Fixed submission:
import itertools

N = int(input())
A = tuple(map(int, input().split()))
S = [0] + list(itertools.accumulate(A))

dp = [[0] * (N + 1) for _ in range(N + 1)]
for length in range(2, N + 1):
    for l in range(N - length + 1):
        r = length + l
        dp[l][r] = min(dp[l][m] + dp[m][r] for m in range(l + 1, r)) + S[r] - S[l]
print(dp[0][N])
Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np

N = int(input())
A = [np.flatnonzero(np.array(list(map(int, input().split())))) for _ in range(N)]

MOD = 10 ** 9 + 7
dp = np.zeros(1 << N, dtype=np.int64)
dp[0] = 1
for a in A:
    new_dp = np.zeros_like(dp)
    for i in a:
        x = (1 << i)
        new_dp[x:] += dp[:-x]
    dp = new_dp
    dp %= MOD
print(dp[-1])


Fixed submission:
N = int(input())
A = [tuple(map(int, input().split())) for _ in range(N)]
MOD = 10 ** 9 + 7

dp = [0] * (1 << N)
dp[0] = 1
for b in range(1, 1 << N):
    i = bin(b).count('1')
    for x in range(N):
        if (b >> x) & 1 and A[i - 1][x]:
            dp[b] += dp[b ^ (1 << x)]
    dp[b] %= MOD
print(dp[-1])

Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np

N = int(input())
A = []
for _ in range(N):
    arr = np.array(list(map(int, input().split())))
    A.append(np.flatnonzero(arr))

MOD = 10 ** 9 + 7
dp = np.zeros(1 << N, dtype=np.int64)
dp[0] = 1
for a in A:
    new_dp = np.zeros_like(dp)
    for i in a:
        x = (1 << i)
        new_dp[x:] += dp[:-x]
    dp = new_dp
    dp %= MOD
print(dp[-1])


Fixed submission:
N = int(input())
A = [tuple(map(int, input().split())) for _ in range(N)]
MOD = 10 ** 9 + 7

dp = [0] * (1 << N)
dp[0] = 1
for b in range(1, 1 << N):
    i = bin(b).count('1')
    for x in range(N):
        if (b >> x) & 1 and A[i - 1][x]:
            dp[b] += dp[b ^ (1 << x)]
    dp[b] %= MOD
print(dp[-1])