Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    from collections import deque
    import sys
    input = sys.stdin.readline

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

    g = tuple(set() for _ in range(N * 3))
    for _ in range(M):
        u, v = (int(x) - 1 for x in input().split())
        g[u].add(v + N)
        g[u + N].add(v + N * 2)
        g[u + N * 2].add(v)

    S, T = (int(x) - 1 for x in input().split())

    dist = [-1] * (N * 3)
    dist[S] = 0

    dq = deque()
    dq.append(S)

    while dq:
        v = dq.popleft()
        d = dist[v]
        for u in g[v]:
            if (~dist[u]) and (dist[u] < d): continue
            dist[u] = d + 1
            dq.append(u)

    ans = dist[T] // 3

    print(ans)


if __name__ == '__main__':
    main()


Fixed submission:
from collections import deque

inf = float('inf')

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

es = [[] for _ in range(N * 3)]
# 有向グラフ

for _ in range(M):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    # 0-indexed
    es[u].append(v + N)
    es[u + N].append(v + N * 2)
    es[u + N * 2].append(v)

S, T = map(int, input().split())
S -= 1
T -= 1

dq = deque([(S, 0)])
dist = [inf] * (N * 3)
dist[S] = 0

while dq:
    v, c = dq.popleft()
    nc = c + 1
    for nv in es[v]:
        if nc < dist[nv]:
            dist[nv] = nc
            if v == T:
                break
            dq.append((nv, nc))

if dist[T] == inf:
    print(-1)
else:
    print(dist[T] // 3)

# print(dist)
Buggy python submission (verdict: Runtime Error):
def main():
    from collections import Counter, namedtuple

    pt = namedtuple('pt', 'x y')

    def delta(a: pt, b: pt) -> pt:
        x = a.x - b.x
        y = a.y - b.y
        if x < 0:
            x = -x
            y = -y
        return pt(x=x, y=y)

    n = int(input())
    ps = [pt(*map(int, input().split())) for _ in range(n)]

    c = Counter(
        delta(a, b)
        for i, a in enumerate(ps)
        for j, b in enumerate(ps)
        if i < j
    )

    ma = max(c.values())

    print(n - ma)


if __name__ == '__main__':
    main()


Fixed submission:
from collections import defaultdict
from operator import itemgetter

N = int(input())
p = []
for _ in range(N):
    p.append(tuple(map(int, input().split())))
p.sort(key=itemgetter(0), reverse=True)

if N == 1:
    print(1)
else:
    d = defaultdict(int)
    for i, pp1 in enumerate(p):
        for j in range(i + 1, N):
            pp2 = p[j]
            d[(pp1[0] - pp2[0], pp1[1] - pp2[1])] += 1
        # print(d)

    cnt = 0
    keys = tuple(d.keys())
    for k in keys:
        x, y = k
        cnt = max(cnt, d[k] + d[(-x, -y)])

    print(N - cnt)

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

N = int(input())

p = []
for _ in range(N):
    p.append(tuple(map(int, input().split())))

d = []
for i, p1 in enumerate(p):
    for j, p2 in enumerate(p):
        if i == j:
            continue
        x = p1[0] - p2[0]
        y = p1[1] - p2[1]
        d.append((x, y))

c = Counter(d)
# print(c)
print(N - c.most_common()[0][1])


Fixed submission:
from collections import defaultdict
from operator import itemgetter

N = int(input())
p = []
for _ in range(N):
    p.append(tuple(map(int, input().split())))
p.sort(key=itemgetter(0), reverse=True)

if N == 1:
    print(1)
else:
    d = defaultdict(int)
    for i, pp1 in enumerate(p):
        for j in range(i + 1, N):
            pp2 = p[j]
            d[(pp1[0] - pp2[0], pp1[1] - pp2[1])] += 1
        # print(d)

    cnt = 0
    keys = tuple(d.keys())
    for k in keys:
        x, y = k
        cnt = max(cnt, d[k] + d[(-x, -y)])

    print(N - cnt)

Buggy python submission (verdict: Runtime Error):
from collections import Counter
from operator import itemgetter

N = int(input())
p = []
for _ in range(N):
    p.append(tuple(map(int, input().split())))
p.sort(key=itemgetter(0), reverse=True)

d = []
for i, pp1 in enumerate(p):
    for j in range(i + 1, N):
        pp2 = p[j]
        d.append((pp1[0] - pp2[0], pp1[1] - pp2[1]))

c = Counter(d)

print(N - c.most_common()[0][1])


Fixed submission:
from collections import defaultdict
from operator import itemgetter

N = int(input())
p = []
for _ in range(N):
    p.append(tuple(map(int, input().split())))
p.sort(key=itemgetter(0), reverse=True)

if N == 1:
    print(1)
else:
    d = defaultdict(int)
    for i, pp1 in enumerate(p):
        for j in range(i + 1, N):
            pp2 = p[j]
            d[(pp1[0] - pp2[0], pp1[1] - pp2[1])] += 1
        # print(d)

    cnt = 0
    keys = tuple(d.keys())
    for k in keys:
        x, y = k
        cnt = max(cnt, d[k] + d[(-x, -y)])

    print(N - cnt)
Buggy python submission (verdict: Time Limit Exceeded):
from heapq import heapify, heappop, heappush
import sys

input = sys.stdin.readline

N = int(input())
es = [[] for idx in range(N)]
# es[idx]:=[隣接リスト]

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

h = [len(es[i]) for i in range(N)]
# 次数

c = list(map(int, input().split()))
c.sort()
# スコアが小さい順にソート

v = [-1] * N
cur = 0

t = [(e, i) for i, e in enumerate(h, 0)]
heapify(t)
while t:
    g, i = heappop(t)
    # print(h, (g, i), v)
    if g > 1:
        heappush(t, (h[i], i))
    elif g == 1:
        v[i] = c[cur]
        h[i] -= 1
        for nv in es[i]:
            h[nv] -= 1
        cur += 1
# print(h, (g, i), v)
ans = sum(c) - c[-1]
print(ans)
v = [vv if vv != -1 else c[-1] for vv in v]
print(' '.join(map(str, v)))


Fixed submission:
N = int(input())
es = [[] for idx in range(N)]
# es[idx]:=[隣接リスト]

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

h = [len(es[i]) for i in range(N)]
# 次数

c = list(map(int, input().split()))
c.sort()
# スコアが小さい順にソート

v = [-1] * N
cur = 0
ans = 0
for _ in range(N - 1):
    for target in range(N):
        # print(target, h, v, ans)
        if h[target] == 1:
            h[target] = 0
            v[target] = c[cur]
            ans += c[cur]
            cur += 1
            for nv in es[target]:
                h[nv] -= 1
            break
for target in range(N):
    if v[target] == -1:
        v[target] = c[cur]
print(ans)
print(*v, sep='\n')

Buggy python submission (verdict: Time Limit Exceeded):
from operator import itemgetter

N = int(input())
h = [[0, i] for i in range(N)]
# 次数と頂点番号

es = [[] for idx in range(N)]
# es[idx]:=[隣接リスト]

for _ in range(N - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    es[a].append(b)
    h[a][0] += 1
    es[b].append(a)
    h[b][0] += 1

c = list(map(int, input().split()))
c.sort()
# スコアが小さい順にソート

v = [-1] * N
ans = 0

cur = 0
for _ in range(N):
    t = list(sorted(h, key=itemgetter(0)))
    # print(t)
    idx = t[cur][1]
    v[idx] = c[cur]
    ans += c[cur]
    h[idx][0] -= 1
    for nv in es[idx]:
        h[nv][0] -= 1
    cur += 1
ans -= c[-1]
# print(t)
print(ans)
print(*v)


Fixed submission:
N = int(input())
es = [[] for idx in range(N)]
# es[idx]:=[隣接リスト]

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

h = [len(es[i]) for i in range(N)]
# 次数

c = list(map(int, input().split()))
c.sort()
# スコアが小さい順にソート

v = [-1] * N
cur = 0
ans = 0
for _ in range(N - 1):
    for target in range(N):
        # print(target, h, v, ans)
        if h[target] == 1:
            h[target] = 0
            v[target] = c[cur]
            ans += c[cur]
            cur += 1
            for nv in es[target]:
                h[nv] -= 1
            break
for target in range(N):
    if v[target] == -1:
        v[target] = c[cur]
print(ans)
print(*v, sep='\n')
Buggy python submission (verdict: Time Limit Exceeded):
# https://atcoder.jp/contests/m-solutions2019/submissions/5741430
from operator import mul

MOD = 10 ** 6 + 3


def inv(n):
    return pow(n, MOD - 2, MOD)


def mod_mul(x, y):
    return mul(x, y) % MOD


fact = [1]
for n in range(1, MOD):
    fact.append(mod_mul(fact[-1], n))
    # d>1 の数列を d=1 となる数列に変換する
    # MODの倍数を含む数列の積は0になるので,
    # MODの倍数を含まない区間の積が計算できればよい
    # そのような区間の右端はMOD-1であり,fact[MOD-1]が計算できればよい

Q = int(input())
for _ in range(Q):
    x, d, n = map(int, input().split())

    if x == 0:
        print(0)
        continue

    if d == 0:
        print(pow(x, n, MOD))
        continue

    xd = mod_mul(x, inv(d))
    if MOD - xd < n:
        print(0)
        continue

    dn = pow(d, n, MOD)
    print(mod_mul(mod_mul(fact[xd + n - 1], inv(fact[xd - 1])), dn))


Fixed submission:
# https://atcoder.jp/contests/m-solutions2019/submissions/5741430
from operator import mul
import sys

input = sys.stdin.readline

MOD = 10 ** 6 + 3


def inv(n):
    return pow(n, MOD - 2, MOD)


def mod_mul(x, y):
    return mul(x, y) % MOD


fact = [1]
for n in range(1, MOD):
    fact.append(mod_mul(fact[-1], n))
    # d>1 の数列を d=1 となる数列に変換する
    # MODの倍数を含む数列の積は0になるので,
    # MODの倍数を含まない区間の積が計算できればよい
    # そのような区間の右端はMOD-1であり,fact[MOD-1]が計算できればよい

Q = int(input())
for _ in range(Q):
    x, d, n = map(int, input().split())

    if x == 0:
        print(0)
        continue

    if d == 0:
        print(pow(x, n, MOD))
        continue

    xd = mod_mul(x, inv(d))
    if MOD - xd < n:
        print(0)
        continue

    dn = pow(d, n, MOD)
    print(mod_mul(mod_mul(fact[xd + n - 1], inv(fact[xd - 1])), dn))
Buggy python submission (verdict: Runtime Error):
def dfs(v):
    for u, w in e[v]:
        if c[u] != -1:
            continue
        c[u] = (c[v] + w) % 2
        dfs(u)


n = int(input())
e = tuple(set() for _ in range(n))
for _ in range(n - 1):
    u, v, w = map(int, input().split())
    u -= 1
    v -= 1
    e[u].add((v, w))
    e[v].add((u, w))

c = [-1] * n
c[0] = 0

dfs(0)

print(*c, sep='\n')


Fixed submission:
import sys

sys.setrecursionlimit(10 ** 9)


class UnionFind:
    def __init__(self, n):
        self.v = [-1 for _ in range(n)]  # 根(負): 連結頂点数 * (-1) / 子(正): 根の頂点番号(0-indexed)

    def find(self, x):  # xを含む木における根の頂点番号を返す
        if self.v[x] < 0:  # (負)は根
            return x
        else:  # 根の頂点番号
            self.v[x] = self.find(self.v[x])  # uniteでは, 旧根に属する頂点の根が旧根のままなので更新
            return self.v[x]

    def unite(self, x, y):  # 違う根に属していたらrankが低くなるように連結
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if -self.v[x] < -self.v[y]:  # size比較, 　(-1) * (連結頂点数 * (-1)), (正)同士の大小比較
            x, y = y, x  # 連結頂点数が少ない方をyにすると, findでの更新回数が減る？
        self.v[x] += self.v[y]  # 連結頂点数の和を取る, 連結頂点数 * (-1)
        self.v[y] = x  # 連結頂点数が少ないy(引数yの根の頂点番号)の根をx(引数xの根の頂点番号)にする

    def root(self, x):
        return self.v[x] < 0  # (負)は根

    def same(self, x, y):
        return self.find(x) == self.find(y)  # 同じ根に属するか

    def size(self, x):
        return -self.v[self.find(x)]  # 連結頂点数を返す


N = int(input())
e = [[] for _ in range(N)]
uf = UnionFind(N)
for _ in range(N - 1):
    u, v, w = map(int, input().split())
    u -= 1
    v -= 1
    # 0-indexedに直した
    e[u].append((v, w))
    e[v].append((u, w))

    uf.same(u, v)

# e[点]:=(隣接頂点,長さ)

root = uf.find(0)
# 根

ans = [None] * N
ans[root] = 0

# print(e)


def rec(vv):
    for nv, w in e[vv]:
        if ans[nv] is not None: continue
        ans[nv] = (ans[vv] + w) % 2
        rec(nv)


rec(root)

print(*ans, sep='\n')
Buggy python submission (verdict: Runtime Error):
M, K = map(int, input().split())

if K >= 2 ** M:
    print(-1)
elif K == 0:
    ans = []
    x = range(0, 2 ** M)
    y = range(0, 2 ** M)
    for xx, yy in zip(x, y):
        ans.append(xx)
        ans.append(yy)
    print(*ans)
else:
    t = 0
    for i in range(1, 2 ** M):
        if i == K: continue
        t ^= i
    if t == K:
        x = [i for i in range(0, 2 ** M) if i != K]
        ans = [K] + x + [K] + reversed(x)
        print(*ans)
    else:
        print(-1)


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

if K >= 2 ** M:
    print(-1)
elif K == 0:
    ans = []
    x = range(0, 2 ** M)
    y = range(0, 2 ** M)
    for xx, yy in zip(x, y):
        ans.append(xx)
        ans.append(yy)
    print(*ans)
else:
    t = 0
    for i in range(1, 2 ** M):
        if i == K: continue
        t ^= i
    if t == K:
        x = [i for i in range(0, 2 ** M) if i != K]
        ans = [K] + x + [K] + list(reversed(x))
        print(*ans)
    else:
        print(-1)
Buggy python submission (verdict: Runtime Error):
from bisect import bisect_left

n = int(input())
a = tuple(sorted(map(int, input().split())))
j = bisect_left(a, 0)

p = a[j:]
m = a[:j]

if len(m) % 2 == 0:
    print(sum(p) - sum(m))
else:
    print(sum(p[1:]) - sum(m[:-1]) + abs(p[0] + m[-1]))


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

sa = 0
min_v = float('inf')
minus_count = 0
for aa in a:
    if aa < 0:
        minus_count += 1
        aa = abs(aa)
    min_v = min(min_v, aa)
    sa += aa

if minus_count % 2 == 0:
    print(sa)
else:
    print(sa - min_v * 2)

Buggy python submission (verdict: Runtime Error):
import numpy as np
from math import inf

N = int(input())
a = map(int, input().split())

dp = np.zeros((N + 1, 2))
dp[0][1] = -inf
# dp[i][0]:=1-indexedで、a_iとa_i+1を反転させない場合の最大値
# dp[i][1]:=1-indexedで、a_iとa_i+1を反転させる場合の最大値

for i, aa in enumerate(a, 0):
    dp[i + 1][0] = max(dp[i][0] + aa, dp[i][1] - aa)
    dp[i + 1][1] = max(dp[i][0] - aa, dp[i][1] + aa)
print(dp[N][0])


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

sa = 0
min_v = float('inf')
minus_count = 0
for aa in a:
    if aa < 0:
        minus_count += 1
        aa = abs(aa)
    min_v = min(min_v, aa)
    sa += aa

if minus_count % 2 == 0:
    print(sa)
else:
    print(sa - min_v * 2)
Buggy python submission (verdict: Time Limit Exceeded):
N, K = map(int, input().split())
s = input()

t = []
cur = s[0]
cnt = 0
for ss in s:
    if cur == ss:
        cnt += 1
    else:
        sgn = 1 if cur == '1' else -1
        # 逆立ちでないなら-1
        t.append(cnt * sgn)

        cur = ss
        cnt = 1
sgn = 1 if cur == '1' else -1
# 逆立ちでないなら-1
t.append(cnt * sgn)

M = len(t)
ans = 0
for i in range(M):
    cnt = 0
    b = 0
    for j in range(i, M):
        if t[j] < 0:
            cnt += 1
            if cnt > K:
                break
            b += -t[j]
        else:
            b += t[j]
    ans = max(ans, b)
print(ans)


Fixed submission:
from bisect import bisect_right

N, K = map(int, input().split())
s = input()

t = []
abs_t = []

cur = s[0]
cnt = 0
for ss in s:
    if cur == ss:
        cnt += 1
    else:
        sgn = 1 if cur == '1' else -1
        # 逆立ちでないなら-1
        t.append(cnt * sgn)
        abs_t.append(cnt)

        cur = ss
        cnt = 1
sgn = 1 if cur == '1' else -1
# 逆立ちでないなら-1
t.append(cnt * sgn)
abs_t.append(cnt)

M = len(t)

sgn_cnt = [0]
for tt in t:
    sgn_cnt.append(sgn_cnt[-1] + (1 if tt < 0 else 0))
# 反転が必要な箇所数の累積和

c_abst = [0]
for att in abs_t:
    c_abst.append(c_abst[-1] + att)

# print(t, abs_t, c_abst, sgn_cnt)

ans = 0
for i in range(M):
    ok = bisect_right(sgn_cnt, (K + sgn_cnt[i]))
    ok -= 1
    # print(ok, i, K + sgn_cnt[i])
    # print(c_abst)
    ans = max(ans, c_abst[min(ok, M)] - c_abst[i])
print(ans)
Buggy python submission (verdict: Runtime Error):
def main():
    from math import gcd

    A, B, K = map(int, input().split())

    g = gcd(A, B)
    rt = int(pow(g, 0.5))

    divisors = set()
    for d in range(1, rt + 1):
        if g % d == 0:
            divisors.add(d)
            divisors.add(g // d)

    ans = sorted(divisors, reverse=True)[K - 1]
    print(ans)


if __name__ == '__main__':
    main()

# import sys
#
# sys.setrecursionlimit(10 ** 7)
#
# input = sys.stdin.readline
# rstrip()
# int(input())
# map(int, input().split())


Fixed submission:
a, b, k = map(int, input().split())
cnt = 0
for i in sorted(range(1, 100 + 1), reverse=True):
    if a % i == 0 and b % i == 0:
        cnt += 1
        if cnt == k:
            print(i)
            exit()
Buggy python submission (verdict: Runtime Error):
a,b=map(int,input().split())
if b%a=0:
  print(a+b)
else:
  print(b-a)


Fixed submission:
a,b=map(int,input().split())
if b%a==0:
  print(a+b)
else:
  print(b-a)

Buggy python submission (verdict: Runtime Error):
a,b=map(int,input().split())
if b % a = 0:
  print(a+b)
else:
  print(b-a)


Fixed submission:
a,b=map(int,input().split())
if b%a==0:
  print(a+b)
else:
  print(b-a)

Buggy python submission (verdict: Runtime Error):
if b % a = 0:
  print(a+b)
else:
  print(b-a)

Fixed submission:
a,b=map(int,input().split())
if b%a==0:
  print(a+b)
else:
  print(b-a)
Buggy python submission (verdict: Runtime Error):
s = input()
ls = len(s)

t = 'keyence'
idx = 0

for i in range(ls):
    if s[i] == t[idx]:
        idx += 1

if idx == len(t):
    print('YES')
else:
    print('NO')


Fixed submission:
import re

s = input()
t = 'keyence'

for i in range(len(t)):
    ptn = '^' + t[:i] + '.*' + t[i:] + '$'
    # print(ptn)
    m = re.match(ptn, s)
    if m: break

if m:
    print('YES')
else:
    print('NO')
Buggy python submission (verdict: Runtime Error):
from bisect import bisect_left

MOD = 10 ** 9 + 7

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

a = list(map(int, input().split()))
a = sorted(a)
la = len(a)
sa = set(a)
lsa = len(sa)
if la != lsa:
    print(0)
    exit()

b = list(map(int, input().split()))
b = sorted(b)
lb = len(b)
sb = set(b)
lsb = len(sb)
if lb != lsb:
    print(0)
    exit()

ans = 1
ai = 0
bi = 0
k = N * M
d = 0
while k > 0:
    ai = bisect_left(a, k)
    bi = bisect_left(b, k)

    if a[ai] == k:
        ta = 1
        if b[bi] == k:
            tb = 1
            t = ta * tb
        else:
            tb = (lb - bi)
            t = ta * tb
    else:
        ta = (la - ai)
        if b[bi] == k:
            tb = 1
            t = ta * tb
        else:
            tb = (lb - bi)
            t = ta * tb - d

    # print(ta, tb)
    ans *= t

    ans %= MOD
    # print(ans)
    k -= 1
    d += 1

print(ans)


Fixed submission:
from bisect import bisect_left

MOD = 10 ** 9 + 7

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

a = list(map(int, input().split()))
a = sorted(a)
la = len(a)
sa = set(a)
lsa = len(sa)
if la != lsa:
    print(0)
    exit()

b = list(map(int, input().split()))
b = sorted(b)
lb = len(b)
sb = set(b)
lsb = len(sb)
if lb != lsb:
    print(0)
    exit()

ans = 1
ai = 0
bi = 0
k = N * M
d = 0
while k > 0:
    ai = bisect_left(a, k)
    bi = bisect_left(b, k)
    
    if ai == la or bi == lb:
        print(0)
        exit()
        
    if a[ai] == k:
        ta = 1
        if b[bi] == k:
            tb = 1
            t = ta * tb
        else:
            tb = (lb - bi)
            t = ta * tb
    else:
        ta = (la - ai)
        if b[bi] == k:
            tb = 1
            t = ta * tb
        else:
            tb = (lb - bi)
            t = ta * tb - d

    # print(ta, tb)
    ans *= t

    ans %= MOD
    # print(ans)
    k -= 1
    d += 1

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import sys

input = sys.stdin.readline

N, W = map(int, input().split())
w, v = [], []
for _ in range(N):
    tw, tv = map(int, input().split())
    w.append(tw)
    v.append(tv)

dp = [[float('inf') for _ in range(sum(v) + 1)] for _ in range(N + 1)]
dp[0][0] = 0
# dp[何番目までの品物で][この価値以下を達成する]:=最小の重量

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

for j in sorted(range(sum(v) + 1), reverse=True):
    t = dp[N][j]
    if t <= W:
        print(j)
        break


Fixed submission:
INF = 10 ** 12
MV = 10 ** 5

N, W = map(int, input().split())
dp = [[INF for _ in range(MV + 1)] for _ in range(N + 1)]
dp[0][0] = 0
# dp[品物のidx][価値の総和] = 実現する最小重量

for i in range(1, N + 1):
    w, v = map(int, input().split())
    for j in range(MV + 1):
        if j - v >= 0:
            dp[i][j] = min(dp[i - 1][j], dp[i - 1][j - v] + w)
        else:
            dp[i][j] = dp[i - 1][j]

ans = -1
j = MV
while j >= 0:
    if dp[N][j] <= W:
        ans = j
        break
    j -= 1
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
V_TOTAL_MAX = 10 ** 5
INF = float('inf')

N, W = map(int, input().split())
dp = [[INF for _ in range(V_TOTAL_MAX + 1)] for _ in range(N + 1)]  # dp[品物番号][基準となる価値] = 重さの総和の最小値
dp[0][0] = 0

for i in range(1, N + 1):
    w, v = map(int, input().split())
    for j in range(0, V_TOTAL_MAX + 1):
        if j < v:
            dp[i][j] = dp[i - 1][j]
        else:
            dp[i][j] = min(dp[i - 1][j], dp[i - 1][j - v] + w)

ans = 0
for j in range(0, V_TOTAL_MAX + 1):
    if dp[N][j] <= W:
        ans = max(ans, j)

print(ans)


Fixed submission:
INF = 10 ** 12
MV = 10 ** 5

N, W = map(int, input().split())
dp = [[INF for _ in range(MV + 1)] for _ in range(N + 1)]
dp[0][0] = 0
# dp[品物のidx][価値の総和] = 実現する最小重量

for i in range(1, N + 1):
    w, v = map(int, input().split())
    for j in range(MV + 1):
        if j - v >= 0:
            dp[i][j] = min(dp[i - 1][j], dp[i - 1][j - v] + w)
        else:
            dp[i][j] = dp[i - 1][j]

ans = -1
j = MV
while j >= 0:
    if dp[N][j] <= W:
        ans = j
        break
    j -= 1
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    from decimal import Decimal
    import sys
    readline = sys.stdin.readline

    n = int(readline())
    *p, = (Decimal(pi) for pi in readline().rstrip().split())

    dp = [[0] * (n + 1) for _ in range(n + 1)]
    dp[0][0] = 1
    # dp[投げた枚数][表の枚数] = 確率

    for i, pi in enumerate(p, 1):
        for j in range(i + 1):
            dp[i][j] += dp[i - 1][j] * (1 - pi) + dp[i - 1][j - 1] * pi

    ret = sum(dp[n][j] for j in reversed(range(n + 1)) if j * 2 > n)
    print(ret)


if __name__ == '__main__':
    main()


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

dp = [[0] * (N + 1) for _ in range(N + 1)]
dp[0][0] = 1

for i in range(1, N + 1):
    for j in range(i + 1):
        dp[i][j] = (dp[i - 1][j] * (1 - p[i - 1])) + (dp[i - 1][j - 1] * p[i - 1])

ans = 0
for j in range(N // 2 + 1, N + 1):
    ans += dp[N][j]
print(ans)
# print(dp)

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
p = tuple(map(float, input().split()))

dp = [[0] * (N + 1) for _ in range(N + 1)]
dp[0][0] = 1

for i in range(1, N + 1):
    for j in range(i + 1):
        dp[i][j] = (dp[i - 1][j] * (1 - p[i - 1])) + (dp[i - 1][j - 1] * p[i - 1])

ans = 0
for j in range(N // 2 + 1, N + 1):
    ans += dp[N][j]
print(ans)
# print(dp)

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

dp = [[0] * (N + 1) for _ in range(N + 1)]
dp[0][0] = 1

for i in range(1, N + 1):
    for j in range(i + 1):
        dp[i][j] = (dp[i - 1][j] * (1 - p[i - 1])) + (dp[i - 1][j - 1] * p[i - 1])

ans = 0
for j in range(N // 2 + 1, N + 1):
    ans += dp[N][j]
print(ans)
# print(dp)
Buggy python submission (verdict: Time Limit Exceeded):
N, P = map(int, input().split())

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

t = 1
pm = 2
while pm ** N <= P:
    e = 0
    while P % pm == 0:
        P //= pm
        e += 1 # 素数のカウント
    t *= pm ** (e // N)
    pm += 1

print(t)


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

if N == 1:
    ans = P
else:
    ans = 1
    p = 2
    while p * p <= P:
        e = 0
        while P % p == 0:
            P //= p
            e += 1  # 素数のカウント
        if e // N > 0:
            ans *= p ** (e // N)
        p += 1

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
import itertools, functools, math


def prime_stream():
    stream = itertools.count(2)
    sieve = lambda x, y: x % y != 0

    while True:
        prime = next(stream)
        stream = filter(functools.partial(sieve, y=prime), stream)
        yield prime


N, P = map(int, input().split())

ans = 1
if P // N != 0:
    for p in prime_stream():
        if p > P:
            break
        e = 0
        while P % p == 0:
            P //= p
            e += 1  # 素数のカウント
        if e // N > 0:
            ans *= p ** (e // N)

print(ans)


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

if N == 1:
    ans = P
else:
    ans = 1
    p = 2
    while p * p <= P:
        e = 0
        while P % p == 0:
            P //= p
            e += 1  # 素数のカウント
        if e // N > 0:
            ans *= p ** (e // N)
        p += 1

print(ans)