Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
def main():
    N, K = map(int, input().split())
    TD = [tuple(map(int, input().split())) for _ in range(N)]
    TD.sort(key=lambda x: x[1], reverse=True)
    s = set()
    rep = []
    for t, d in TD[:K]:
        if t in s:
            rep.append(d)
        else:
            s.add(t)
    m = sum(d for _, d in TD[:K])
    p = len(s) ** 2 + m
    for t, d in TD[K:]:
        if t in s:
            continue
        m += d - rep.pop()
        s.add(t)
        p = max(p, len(s) ** 2 + m)
        if not rep:
            break
    return p

print(main())


Fixed submission:
def main():
    N, K = map(int, input().split())
    TD = [tuple(map(int, input().split())) for _ in range(N)]
    TD.sort(key=lambda x: x[1], reverse=True)
    s = set()
    rep = []
    for t, d in TD[:K]:
        if t in s:
            rep.append(d)
        else:
            s.add(t)
    m = sum(d for _, d in TD[:K])
    p = len(s) ** 2 + m
    for t, d in TD[K:]:
        if not rep:
            break
        if t in s:
            continue
        m += d - rep.pop()
        s.add(t)
        p = max(p, len(s) ** 2 + m)
    return p

print(main())
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    N, W = map(int, input().split())
    wi, vi = map(int, input().split())
    dp = [0] * wi + [vi] * (W + 1 - wi)
    for _ in range(1, N):
        wi, vi = map(int, input().split())
        dp[wi:] = [max(i + vi, j) for i, j in zip(dp, dp[wi:])]
    print(dp[-1])


if __name__ == '__main__':
    main()


Fixed submission:
def main():
    N, W = map(int, input().split())
    wi, vi = map(int, input().split())
    dp = [0] * wi + [vi] * (W + 1 - wi)
    for _ in range(1, N):
        wi, vi = map(int, input().split())
        for i in range(W, wi - 1, -1):
            t = dp[i - wi] + vi
            if t > dp[i]:
                dp[i] = t
    print(dp[-1])


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Runtime Error):
def main():
    N, W = map(int, input().split())
    wi, vi = map(int, input().split())
    dp = [0] * wi + [vi] * (W + 1 - wi)
    for _ in range(1, N):
        wi, vi = map(int, input().split())
        for i in range(W, wi - 1, -1):
            t = dp[i - wi] + vi
            if t > dp[i]:
                dp[i] = t
    print(dp[-1])


if __name__ == '__main__':
    main()


Fixed submission:
def printdp(dp):
    return
    print({i:v for i, v in enumerate(dp) if v < 10000})

def main():
    N, W = map(int, input().split())
    wv = [tuple(map(int, input().split())) for _ in range(N)]
    V = sum(v for _, v in wv)
    dp = [0] + [float('inf')] * V
    for wi, vi in wv:
        for i in range(V, vi - 1, -1):
            t = dp[i - vi] + wi
            if t < dp[i]:
                dp[i] = t
    for i in range(V, -1, -1):
        if dp[i] <= W:
            print(i)
            return


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
from functools import lru_cache
import sys
sys.setrecursionlimit(10 ** 6)

@lru_cache(maxsize=None)
def dp(k, A, turn):
    for i in A:
        if i > k:
            break
        if dp(k - i, A, not turn) == turn:
            return turn
    return not turn
    

def main():
    N, K = map(int, input().split())
    A = tuple(sorted(map(int, input().split())))
    print('First' if dp(K, A, True) else 'Second')


main()


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


def main():
    N, K = map(int, input().split())
    A = tuple(sorted(map(int, input().split())))
    c = [0] * (K + 1)
    def dp(k, A, c, turn):
        if c[k] != 0:
            return c[k] * turn
        for i in A:
            if i > k:
                break
            if dp(k - i, A, c, -turn) == turn:
                c[k] = 1
                return turn
        c[k] = -1
        return -turn
    
    print('First' if dp(K, A, c, 1) == 1 else 'Second')


main()
Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10 ** 6)


def main():
    N = int(input())
    A = list(map(int, input().split()))
    c = [[None] * N for _ in range(N)]
    for r in reversed(range(N)):
        c[r][r] = A[r]
        for l in range(r + 1, N):
            c[r][l] = max(-c[r + 1][l] + A[r], -c[r][l - 1] + A[l])
    
    print(c[0][N - 1])


main()


Fixed submission:
def main():
    N = int(input())
    A = list(map(int, input().split()))
    c = [0] * N
    for r in reversed(range(N)):
        ar = A[r]
        c[r] = t = ar
        for l in range(r + 1, N):
            c[l] = t = max(ar - c[l], A[l] - t)
    
    print(c[-1])


main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10 ** 6)


def main():
    N = int(input())
    A = list(map(int, input().split()))
    c = [[None] * (N + 1) for _ in range(N + 1)]
    def dp(r, l, A, c):
        if r == l:
            return A[r]
        if c[r][l] != None:
            return c[r][l]
        t = max(-dp(r + 1, l, A, c) + A[r],
                -dp(r, l - 1, A, c) + A[l])
        c[r][l] = t
        return t
    
    print(dp(0, N - 1, A, c))


main()


Fixed submission:
def main():
    N = int(input())
    A = list(map(int, input().split()))
    c = [0] * N
    for r in reversed(range(N)):
        ar = A[r]
        c[r] = t = ar
        for l in range(r + 1, N):
            c[l] = t = max(ar - c[l], A[l] - t)
    
    print(c[-1])


main()
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    N = int(input())
    A = list(map(int, input().split()))
    dp = [[0] * (len(A) - i) for i in range(len(A))]

    for i in range(1, len(A)):
        s = sum(A[:i])
        for j in range(len(A) - i):
            s += A[i + j]
            dp[i][j] = min(dp[k][j] + dp[i - k - 1][j + k + 1] for k in range(i)) + s
            s -= A[j]
    print(dp[-1][0])


main()


Fixed submission:
def main():
    N = int(input())
    A = list(map(int, input().split()))
    dp = [[0] * (len(A) - i) for i in range(len(A))]

    for i in range(1, len(A)):
        s = sum(A[:i])
        for j in range(len(A) - i):
            s += A[i + j]
            dp[i][j] = min(dp[k][j] + dp[i - k - 1][j + k + 1] for k in range(i)) + s
            s -= A[j]
    print(dp[-1][0])


main()
Buggy python submission (verdict: Time Limit Exceeded):
MOD = 10**9 + 7

def mul(a, b):
    return [
        [sum(aij * bij for aij, bij in zip(ai, bi)) % MOD for bi in zip(*b)]
        for ai in a]

def pow(b, k):
    if k == 1:
        return b
    i = 0
    while 2 ** (i + 1)<= k:
        i += 1

    k -= 2 ** i
    if k > 0:
        t = pow(b, k)
    for j in range(i):
        b = mul(b, b)
    if k > 0:
        b = mul(b, t)
    return b


def main():
    N, K = (int(i) for i in input().split())
    A = []
    for i in range(N):
        A.append([int(j) for j in input().split()])
    A = [i for i in zip(*A)]
    v = [[1] * N]
    return sum(mul(v, pow(A, K))[0]) % MOD

print(main())


Fixed submission:
MOD = 10**9 + 7

def mul(a, b):
    return [
        [sum(aij * bij for aij, bij in zip(ai, bi)) % MOD for bi in zip(*b)]
        for ai in a]

def pow(b, k):
    r = [[1 if i == j else 0 for i in range(len(b))] for j in range(len(b))]
    while k:
        if k & 1:
            r = mul(r, b)
        k >>= 1
        b = mul(b, b)
    return r


def main():
    N, K = (int(i) for i in input().split())
    A = []
    for i in range(N):
        A.append([int(j) for j in input().split()])
    A = [i for i in zip(*A)]
    v = [[1] * N]
    return sum(mul(v, pow(A, K))[0]) % MOD

print(main())
Buggy python submission (verdict: Time Limit Exceeded):
import math

def factor(n):
    i = 2
    r = []
    while i * i <= n:
        if n % i == 0:
            c = 0
            while n % i == 0:
                c += 1
                n //= i
            r.append((i, c))
    if n > 1:
        r.append((n, 1))
    return r

class nCrMod():
    def __init__(self, mod):
        self.mod = mod
        self.fac = [1, 1]
        self.finv = [1, 1]
        self.inv = [0, 1]

    def prep(self, n):
        mod = self.mod
        f, fi = self.fac[-1], self.finv[-1]
        for i in range(len(self.fac), n + 1):
            fn = f * i % mod
            v = -self.inv[mod % i] * (mod // i) % mod
            fin = fi * v % mod
            f, fi = fn, fin
            self.fac.append(f)
            self.finv.append(fi)
            self.inv.append(v)

    def __call__(self, n, r):
        if len(self.fac) <= n:
            self.prep(n)
        return self.fac[n] * self.finv[r] * self.finv[n - r] % self.mod

def main():
    N, M = map(int, input().split())
    mod = 10**9 + 7
    nCr = nCrMod(mod)
    f = factor(M)
    r = 1
    for p, q in f:
        r = r * nCr(N + q - 1, q) % mod
    return r

print(main())


Fixed submission:
import math

def factor(n):
    i = 2
    r = []
    while i * i <= n:
        if n % i == 0:
            c = 0
            while n % i == 0:
                c += 1
                n //= i
            r.append((i, c))
        i += 1
    if n > 1:
        r.append((n, 1))
    return r

class nCrMod():
    def __init__(self, mod):
        self.mod = mod
        self.fac = [1, 1]
        self.finv = [1, 1]
        self.inv = [0, 1]

    def prep(self, n):
        mod = self.mod
        f, fi = self.fac[-1], self.finv[-1]
        for i in range(len(self.fac), n + 1):
            fn = f * i % mod
            v = -self.inv[mod % i] * (mod // i) % mod
            fin = fi * v % mod
            f, fi = fn, fin
            self.fac.append(f)
            self.finv.append(fi)
            self.inv.append(v)

    def __call__(self, n, r):
        if len(self.fac) <= n:
            self.prep(n)
        return self.fac[n] * self.finv[r] * self.finv[n - r] % self.mod

def main():
    N, M = map(int, input().split())
    mod = 10**9 + 7
    nCr = nCrMod(mod)
    f = factor(M)
    r = 1
    for p, q in f:
        r = r * nCr(N + q - 1, q) % mod
    return r

print(main())
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    H, W, D = list(map(int, input().split()))
    b = [None] * (H * W)
    for h in range(H):
        for w, a in enumerate(map(int, input().split())):
            b[a - 1] = (h, w)
    C = [0] * (H * W)
    for i in range(H * W - D):
        hi, wi = b[i]
        hn, wn = b[i + D]
        C[i] = abs(hi - hn) + abs(wi - wn)
    Q = int(input())
    r = 0
    cache = {}
    for _ in range(Q):
        l, r = map(int, input().split())
        if (l, r) not in cache:
            cache[(l, r)] = sum(C[l - 1:r - 1:D])
        print(cache[(l, r)])
        
main()


Fixed submission:
def main():
    H, W, D = list(map(int, input().split()))
    b = [None] * (H * W)
    for h in range(H):
        for w, a in enumerate(map(int, input().split())):
            b[a - 1] = (h, w)
    C = [0] * (H * W)
    for i in range(H * W - D):
        hi, wi = b[i]
        hn, wn = b[i + D]
        C[i] = abs(hi - hn) + abs(wi - wn)
    E = [0] * (H * W)
    for i in reversed(range(H * W - D)):
            E[i] = E[i + D] + C[i]
    Q = int(input())
    for _ in range(Q):
        l, r = map(int, input().split())
        print(E[l - 1] - E[r - 1])
        
main()
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    S = input()
    X, Y = map(int, input().split())
    cur = set([(0, 0, 0)])
    D = [(1, 0), (0, -1), (-1, 0), (0, 1)]
    for s in S:
        nxt = set()
        if s == 'F':
            for x, y, d in cur:
                tx, ty = D[d]
                nxt.add((x + tx, y + ty, d))
        else:
            for x, y, d in cur:
                nxt.add((x, y, (d + 1) % 4))
                nxt.add((x, y, (d - 1) % 4))
        cur = nxt
    return any((X, Y, i) in cur for i in range(4))

print('Yes' if main() else 'No')


Fixed submission:
def main():
    S = input()
    X, Y = map(int, input().split())
    d = 0
    L = [[0], [0]]
    for s in S:
        if s == 'T':
            d = 1 - d
            if L[d][-1] != 0:
                L[d].append(0)
        else:
            L[d][-1] += 1
    xs, ys = set([L[0][0] if S[0] == 'F' else 0]), set([0])
    for i in L[0][1 if S[0] == 'F' else 0:]:
        xs = set(x + i for x in xs) | set(x - i for x in xs)
    for i in L[1]:
        ys = set(y + i for y in ys) | set(y - i for y in ys)
    return X in xs and Y in ys

print('Yes' if main() else 'No')
Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10**7)
from functools import lru_cache

def main():
    N, Z, W = map(int, input().split())
    A = list(map(int, input().split()))
    dp = [0] * N

    @lru_cache(maxsize=None)
    def hoge(z, w, n, turn):
        if n == 0:
            return abs(z - w)
        if turn:
            return max(hoge(A[N - 1 - i], w, i, not turn) for i in range(n))
        else:
            return min(hoge(z, A[N - 1 - i], i, not turn) for i in range(n))
    return hoge(Z, W, N, True)

print(main())


Fixed submission:
def main():
    N, Z, W = map(int, input().split())
    A = list(map(int, input().split()))
    if N == 1:
        return abs(A[-1] - W)
    return max(abs(A[-1] - W), abs(A[-1] - A[-2]))


print(main())

Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10**7)

def main():
    N, Z, W = map(int, input().split())
    A = list(map(int, input().split()))
    dp = [0] * N
    def hoge(z, w, n, turn):
        if n == 0:
            return abs(z - w)
        if turn:
            return max(hoge(A[N - 1 - i], w, i, not turn) for i in range(n))
        else:
            return min(hoge(z, A[N - 1 - i], i, not turn) for i in range(n))
    return hoge(Z, W, N, True)

print(main())


Fixed submission:
def main():
    N, Z, W = map(int, input().split())
    A = list(map(int, input().split()))
    if N == 1:
        return abs(A[-1] - W)
    return max(abs(A[-1] - W), abs(A[-1] - A[-2]))


print(main())

Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10**7)

def main():
    N, Z, W = map(int, input().split())
    A = list(map(int, input().split()))
    dp = [0] * N
    def hoge(z, w, n, turn):
        if n == 0:
            return abs(z - w)
        if turn:
            return max(hoge(A[N - 1 - i], w, i, not turn) for i in range(n))
        else:
            return min(hoge(z, A[N - 1 - i], i, not turn) for i in range(n))
    return hoge(Z, W, N, True)

print(main())


Fixed submission:
def main():
    N, Z, W = map(int, input().split())
    A = list(map(int, input().split()))
    if N == 1:
        return abs(A[-1] - W)
    return max(abs(A[-1] - W), abs(A[-1] - A[-2]))


print(main())
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    N = int(input())
    A = [list(map(int, input().split())) for _ in range(N)]
    r = 0
    for i in range(N):
        for j in range(i + 1, N):
            for k in range(N):
                if k == i or k == j:
                    continue
                if A[i][k] + A[k][j] < A[i][j]:
                    return -1
                if A[i][k] + A[k][j] == A[i][j]:
                    break
            else:
                r += A[i][j]
    return r

print(main())


Fixed submission:
def main():
    N = int(input())
    A = [list(map(int, input().split())) for _ in range(N)]
    r = 0
    for i in range(N):
        for j in range(i + 1, N):
            for k in range(N):
                if k == i or k == j:
                    continue
                if A[i][k] + A[k][j] < A[i][j]:
                    return -1
                if A[i][k] + A[k][j] == A[i][j]:
                    break
            else:
                r += A[i][j]
    return r

print(main())
Buggy python submission (verdict: Runtime Error):
def main():
    N, M = map(int, input().split())
    G = [[] for _ in range(N)]
    for _ in range(M):
        a, b, c = map(int, input().split())
        G[a - 1].append((b - 1, c))
    INF = 10 ** 40
    S = [-INF] * N
    S[0] = 0

    cur = set([0])
    def helper(n, s, hist):
        for g, gc in G[n]:
            if S[g] > s + gc or S[g] >= INF:
                continue
            S[g] = s + gc
            if g in hist:
                S[g] = INF
            hist.add(g)
            helper(g, S[g], hist)
            if g in hist:
                hist.remove(g)
    helper(0, 0, set())
    s = S[-1]
    return s if s < INF else 'inf'

print(main())


Fixed submission:
import sys
sys.setrecursionlimit(10**7)
def main():
    N, M = map(int, input().split())
    G = [[] for _ in range(N)]
    for _ in range(M):
        a, b, c = map(int, input().split())
        G[a - 1].append((b - 1, c))
    INF = 10 ** 40
    S = [-INF] * N
    S[0] = 0

    def helper(n, s, hist):
        for g, gc in G[n]:
            if S[g] >= s + gc or S[g] >= INF:
                continue
            S[g] = s + gc
            if g in hist:
                S[g] = INF
            hist[g] = hist.get(g, 0) + 1
            helper(g, S[g], hist)
            hist[g] -= 1
            if hist[g] == 0:
                del hist[g]
    helper(0, 0, {0: 1})
    s = S[-1]
    return s if s < INF else 'inf'

print(main())
Buggy python submission (verdict: Runtime Error):
import heapq

def main():
    N, M = map(int, input().split())
    G = [[] for _ in range(N)]
    for _ in range(M):
        a, b, c = map(int, input().split())
        G[a - 1].append((b - 1, c))
        G[b - 1].append((a - 1, c))
    used = set()
    for i in range(N):
        H = []
        for b, c in G[i]:
            heapq.heappush(H, (c, i, b))
        todo = set(range(N))
        todo.remove(i)
        D = [10**10] * N
        D[i] = 0
        while H:
            c, a, b = heapq.heappop(H)
            if D[b] < c:
                continue
            D[b] = c
            if a < b:
                used.add((a, b))
            else:
                used.add((b, a))
            todo.remove(b)
            for d, cc in G[b]:
                if d in todo:
                    heapq.heappush(H, (c + cc, b, d))
    return M - len(used)

print(main())


Fixed submission:
import heapq

def main():
    N, M = map(int, input().split())
    G = [[] for _ in range(N)]
    for _ in range(M):
        a, b, c = map(int, input().split())
        G[a - 1].append((b - 1, c))
        G[b - 1].append((a - 1, c))
    used = set()
    for i in range(N):
        H = []
        for b, c in G[i]:
            heapq.heappush(H, (c, i, b))
        D = [10**10] * N
        D[i] = 0
        while H:
            c, a, b = heapq.heappop(H)
            if D[b] < c:
                continue
            D[b] = c
            if a < b:
                used.add((a, b))
            else:
                used.add((b, a))
            for d, cc in G[b]:
                if D[d] > c + cc:
                    D[d] = c + cc
                    heapq.heappush(H, (c + cc, b, d))
    return M - len(used)

print(main())
Buggy python submission (verdict: Runtime Error):
ans_lis = [0 for _ in range(n)]
n = int(input())
for x in range(1,101):
    for y in range(1, 101):
        for z in range(1, 101):
            f = x**2+y**2+z**2+x*y+y*z+z*x
            if f<=n:
#                 print(f)
                ans_lis[f-1]+=1
for ans in ans_lis:
    print(ans)

Fixed submission:

n = int(input())
ans_lis = [0 for _ in range(n)]
for x in range(1,101):
    for y in range(1, 101):
        for z in range(1, 101):
            f = x**2+y**2+z**2+x*y+y*z+z*x
            if f<=n:
                ans_lis[f-1]+=1
for ans in ans_lis:
    print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
a = list(map(int, input().split()))


m = max(a)
for i in range(100):
    if 2**i>m:
        n = i
        break


mat = []
for j in a:
    b=[1 if j >> i &1 else 0 for i in reversed(range(n))] 
    mat.append(b)


for i in range(n):
    f = [part[i] for part in mat]
    if sum(f)%2==0:
        ans = f
#         print(ans)
    else:
        ans = [1 if j==0 else 0 for j in f]
#         print(ans)
    for j in range(len(ans)):
        mat[j][i] = ans[j]
res = []
for m in mat:
    ans = 0
    for i in range(len(m)):
        ans += 2**i*m[-i-1]
    
    res.append(ans)
print(" ".join(map(str,res)))

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


m = max(a)
for i in range(100):
    if 2**i>m:
        n = i
        break


mat = []
for j in a:
    b=[1 if j >> i &1 else 0 for i in reversed(range(n))] 
    mat.append(b)


for i in range(n):
    f = [part[i] for part in mat]
    if sum(f)%2==0:
        ans = f
#         print(ans)
    else:
        ans = [1 if j==0 else 0 for j in f]
#         print(ans)
    for j in range(len(ans)):
        mat[j][i] = ans[j]
res = []
for m in mat:
    ans = 0
    for i in range(len(m)):
        ans += 2**i*m[-i-1]
    
    res.append(ans)
print(" ".join(map(str,res)))
Buggy python submission (verdict: Runtime Error):
import math 
a, b = map(float, input().split())
a =int(100*a)
b = int(100*b)
c = a*b
d = str(c)[:-4]
print(int(d))

Fixed submission:
from decimal import *
a, b = map(str, input().split())
a = Decimal(a)
b = Decimal(b)
c = a*b
e=c.quantize(Decimal('0'), rounding=ROUND_FLOOR)
print(e)
Buggy python submission (verdict: Runtime Error):
A, B, H, M =map(int, input().split())
Min = 60*H + M
long_v = 0.5
short_v = 6
diff = 5.5*Min%360
print((A**2 + B**2 - 2*A*B*math.cos(math.radians(diff)))**0.5)

Fixed submission:
import math
A, B, H, M =map(int, input().split())
Min = 60*H + M
long_v = 0.5
short_v = 6
diff = 5.5*Min%360
print((A**2 + B**2 - 2*A*B*math.cos(math.radians(diff)))**0.5)
Buggy python submission (verdict: Runtime Error):
visited = [False for _ in range(N)]
que = [1]
visited[0] = True
sign = [-1 for _ in range(N)]

while True:
    next_que = []
    if not que:
        break
#     for q in que:
#         probable_room = path[q-1]
#         for p in probable_room:
    else:
        for q in que:
            probable_room = path[q-1]
            for p in probable_room:
#                 if p == q:
#                     continue
                if visited[p-1]:
                    continue
                else:
#                 print(1111)
                    visited[p-1] = True
                    sign[p-1] = q
                    next_que.append(p)
    que = next_que
if all(visited):
    print("Yes")
    for i in range(1,N):
        print(sign[i])
else:
    print("No")
    

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



path = [[] for _ in range(N)]
for _ in range(M):
    A, B = map(int, input().split())
    path[A-1].append(B) 
    path[B-1].append(A)
    
    

visited = [False for _ in range(N)]
que = [1]
visited[0] = True
sign = [-1 for _ in range(N)]

while True:
    next_que = []
    if not que:
        break
#     for q in que:
#         probable_room = path[q-1]
#         for p in probable_room:
    else:
        for q in que:
            probable_room = path[q-1]
            for p in probable_room:
#                 if p == q:
#                     continue
                if visited[p-1]:
                    continue
                else:
#                 print(1111)
                    visited[p-1] = True
                    sign[p-1] = q
                    next_que.append(p)
    que = next_que
if all(visited):
    print("Yes")
    for i in range(1,N):
        print(sign[i])
else:
    print("No")