Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
def gcd(a, b):
    if a > b:
        a, b = b, a
    if a == 0:
        return b

    return gcd(b % a, a)


N = int(input())
A = [int(v) for v in input().split()]
max_gcd = -1

for i in range(N):
    tmp = None
    for j in range(N):
        if j == i: continue
        if tmp is None:
            tmp = A[j]
            continue

        # print(tmp, A[j], gcd(tmp, A[j]))
        tmp = gcd(tmp, A[j])
    max_gcd = max(tmp, max_gcd)
if max_gcd < 0:
    print(A[0])
else:
    print(max_gcd)


Fixed submission:
N = int(input())
A = [int(v) for v in input().split()]


def gcd(a, b):
    if a > b:
        a, b = b, a

    if a == 0: return b
    return gcd(a, b % a)


L = [0 for _ in range(N + 2)]
R = [0 for _ in range(N + 2)]

for i, a in enumerate(A):
    L[i + 1] = gcd(A[i], L[i])
    R[N-i] = gcd(A[N-i-1], R[N-i+1])

# print(L)
# print(R)

res = -2
for i in range(1, N+1):
    res = max(res, gcd(L[i-1], R[i+1]))
print(res)

Buggy python submission (verdict: Time Limit Exceeded):
def gcd(a, b):
    if a > b:
        a, b = b, a
    if a == 0:
        return b

    return gcd(b % a, a)


N = int(input())
A = [int(v) for v in input().split()]
max_gcd = -1

for i in range(N):
    tmp = None
    for j in range(N):
        if j == i: continue
        if tmp is None:
            tmp = A[j]
            continue

        # print(tmp, A[j], gcd(tmp, A[j]))
        tmp = gcd(tmp, A[j])
    max_gcd = max(tmp, max_gcd)
if max_gcd < 0:
    print(A[0])
else:
    print(max_gcd)


Fixed submission:
N = int(input())
A = [int(v) for v in input().split()]


def gcd(a, b):
    if a > b:
        a, b = b, a

    if a == 0: return b
    return gcd(a, b % a)


L = [0 for _ in range(N + 2)]
R = [0 for _ in range(N + 2)]

for i, a in enumerate(A):
    L[i + 1] = gcd(A[i], L[i])
    R[N-i] = gcd(A[N-i-1], R[N-i+1])

# print(L)
# print(R)

res = -2
for i in range(1, N+1):
    res = max(res, gcd(L[i-1], R[i+1]))
print(res)
Buggy python submission (verdict: Time Limit Exceeded):
import heapq

X, Y, Z, K = [int(v) for v in input().split()]
A = [int(v) for v in input().split()]
B = [int(v) for v in input().split()]
C = [int(v) for v in input().split()]

h = []
for i in range(X):
    for j in range(Y):
        for k in range(Z):
            heapq.heappush(h, (-(A[i]+B[j]+C[k]), A[i], B[j], C[k]))

for i in range(K):
    print(sum(heapq.heappop(h)[1:]))

Fixed submission:
import heapq

X, Y, Z, K = [int(v) for v in input().split()]
A = sorted([int(v) for v in input().split()], reverse=True)
B = sorted([int(v) for v in input().split()], reverse=True)
C = sorted([int(v) for v in input().split()], reverse=True)

added = set()
h = [(-(A[0] + B[0] + C[0]), 0, 0, 0)]
added.add((0, 0, 0))
for i in range(K):
    cost, ai, bi, ci = heapq.heappop(h)
    print(-cost)

    if ai + 1 < X:
        na = (ai + 1, bi, ci)
        if not na in added:
            heapq.heappush(h, (-(A[ai + 1] + B[bi] + C[ci]),) + na)
            added.add(na)
    if bi + 1 < Y:
        nb = (ai, bi + 1, ci)
        if not nb in added:
            heapq.heappush(h, (-(A[ai] + B[bi + 1] + C[ci]),) + nb)
            added.add(nb)
    if ci + 1 < Z:
        nc = (ai, bi, ci + 1)
        if not nc in added:
            heapq.heappush(h, (-(A[ai] + B[bi] + C[ci + 1]),) + nc)
            added.add(nc)
Buggy python submission (verdict: Time Limit Exceeded):
N, Q = [int(v) for v in input().split()]
S = input()
for i in range(Q):
    l, r = [int(v) for v in input().split()]
    print(S[l - 1: r].count('AC'))


Fixed submission:
N, Q = [int(v) for v in input().split()]
S = input()

cnt_list = [0] * len(S)
i = 0
for i in range(1, len(S)):

    cnt_list[i] = cnt_list[i - 1]
    if S[i - 1] == 'A' and S[i] == 'C':
        cnt_list[i] += 1

# print(cnt_list)
for i in range(Q):
    l, r = [int(v) for v in input().split()]
    print(cnt_list[r-1] - cnt_list[l-1])
Buggy python submission (verdict: Time Limit Exceeded):
A, B = [int(_) for _ in input().split()]

R = 0
tmp = B
while tmp > 1:
    tmp = tmp // 2
    R += 1
ans = [0] * (R + 1)

memo = [[A, B]]
for i in range(R, -1, -1):
    v = 2 ** i
    for j in range(len(memo)):
        a, b = memo[j]
        if b >= v:
            ans[i] += b - v + 1 - max(a - v, 0)
            if b - v > 0:
                memo.append([max(a - v, 0), b - v])
            if a < v:
                memo[j] = [a, v - 1]
            else:
                memo[j] = [0, 0]

ans = ''.join([str(_ % 2) for _ in reversed(ans)])
print(int(ans, 2))


Fixed submission:
def solve(n):
    """ f(0, n) """

    n += 1
    res = 0
    for i in range(0, 40):
        t2 = (1 << i)
        # i桁の周期が完全に何回でてくるか
        x = n // (t2 * 2)
        cnt = x * t2
        # あまり分(0 * t2 のあと 1 * t2 の順で出現)
        cnt += max(0, n % (t2 * 2) - t2)

        res += t2 * (cnt % 2)
    return res


a, b = [int(_) for _ in input().split()]
# print(solve(b))
# print(solve(a-1))
print(solve(b) ^ solve(a-1))

Buggy python submission (verdict: Time Limit Exceeded):
A, B = [int(_) for _ in input().split()]

R = 0
tmp = B
while tmp > 1:
    tmp = tmp // 2
    R += 1
ans = [0] * (R + 1)

memo = [[A, B]]
for i in range(R, -1, -1):
    v = 2 ** i
    for j in range(len(memo)):
        a, b = memo[j]
        if b >= v:
            ans[i] += b - v + 1 - max(a - v, 0)
            if b - v > 0:
                memo.append([max(a - v, 0), b - v])
            if a < v:
                memo[j] = [a, v - 1]
            else:
                memo[j] = [0, 0]

ans = ''.join([str(_ % 2) for _ in reversed(ans)])
print(int(ans, 2))


Fixed submission:
def solve(n):
    """ f(0, n) """

    n += 1
    res = 0
    for i in range(0, 40):
        t2 = (1 << i)
        # i桁の周期が完全に何回でてくるか
        x = n // (t2 * 2)
        cnt = x * t2
        # あまり分(0 * t2 のあと 1 * t2 の順で出現)
        cnt += max(0, n % (t2 * 2) - t2)

        res += t2 * (cnt % 2)
    return res


a, b = [int(_) for _ in input().split()]
# print(solve(b))
# print(solve(a-1))
print(solve(b) ^ solve(a-1))
Buggy python submission (verdict: Runtime Error):
A,B,C = [int(v) for v in input().split()]
print(max(A//B,C)

Fixed submission:
A,B,C = [int(v) for v in input().split()]
print(min(B//A,C))
Buggy python submission (verdict: Time Limit Exceeded):
S = list(input())


def f():
    global S
    cnt = 0
    pre = ''
    pre_idx = -1
    for i, s in enumerate(S):
        if not s: continue

        if pre and s != pre:
            cnt += 2
            S[i] = ''
            S[pre_idx] = ''
            pre = ''
        else:
            pre = s
            pre_idx = i
    S = [s for s in S if s]
    return cnt


res = 0
while 1:
    tmp = f()
    if not tmp: break
    res += tmp

print(res)


Fixed submission:
S = list(input())
stack = []

res = 0

for s in S:
    if stack and stack[-1] != s:
        stack.pop()
        res += 2
        continue
    stack.append(s)
print(res)

Buggy python submission (verdict: Time Limit Exceeded):
S = list(input())


def f():
    cnt = 0
    pre = ''
    pre_idx = -1
    for i, s in enumerate(S):
        if not s: continue

        if pre and s != pre:
            cnt += 2
            S[i] = ''
            S[pre_idx] = ''
            pre = ''
        else:
            pre = s
            pre_idx = i
    return cnt


res = 0
while 1:
    tmp = f()
    if not tmp: break
    res += tmp

print(res)


Fixed submission:
S = list(input())
stack = []

res = 0

for s in S:
    if stack and stack[-1] != s:
        stack.pop()
        res += 2
        continue
    stack.append(s)
print(res)
Buggy python submission (verdict: Time Limit Exceeded):


N, K = [int(_) for _ in input().split()]
H = [int(_) for _ in input().split()]

memo = [1e12] * (N + 1)
memo[0] = 0

for i in range(N - 1):
    for j in range(1, K + 1):
        if i + j >= N: break
        memo[i + j] = min(abs(H[i] - H[i + j]) + memo[i], memo[i + j])
print(memo[N - 1])


Fixed submission:


N, K = [int(_) for _ in input().split()]
H = [int(_) for _ in input().split()]

memo = [1e12] * (N + 1)
memo[0] = 0

for i in range(N - 1):
    for j in range(1, K + 1):
        if i + j >= N: break
        memo[i + j] = min(abs(H[i] - H[i + j]) + memo[i], memo[i + j])
print(memo[N - 1])
Buggy python submission (verdict: Time Limit Exceeded):
N, W = [int(_) for _ in input().split()]
dp = [0] * (W + 10)  # [[0] * 3 for _ in range(10 ** 5 + 2)]

for i in range(1, N + 1):
    w, v = [int(_) for _ in input().split()]
    for j in range(len(dp) - 1, -1, -1):
        if j + w <= W:
            dp[j + w] = max(dp[j + w], dp[j] + v)

print(max(dp))


Fixed submission:
N, W = [int(_) for _ in input().split()]
dp = [0] * (W + 10)  # [[0] * 3 for _ in range(10 ** 5 + 2)]

for i in range(1, N + 1):
    w, v = [int(_) for _ in input().split()]
    for j in range(len(dp) - 1, -1, -1):
        if j + w <= W:
            dp[j + w] = max(dp[j + w], dp[j] + v)

print(max(dp))
Buggy python submission (verdict: Time Limit Exceeded):
S = list(input())
T = list(input())
MAX_LEN = 3007
dp = [[0] * MAX_LEN for _ in range(MAX_LEN)]

for i in range(len(S)):
    for j in range(len(T)):
        ii = i + 1
        jj = j + 1
        if S[i] == T[j]:
            dp[ii][jj] = dp[ii - 1][jj - 1] + 1
        else:

            dp[ii][jj] = max(dp[ii - 1][jj],
                             dp[ii][jj - 1]
                             )

i = len(S)
j = len(T)
from collections import deque

ans = deque(maxlen=dp[i][j])
while i > 0 and j > 0:
    if dp[i][j] == dp[i][j - 1]:
        j -= 1
    elif dp[i][j] == dp[i - 1][j]:
        i -= 1
    else:
        ans.appendleft(S[i - 1])
        i -= 1
        j -= 1
print(*ans, sep='')


Fixed submission:
s = input()
t = input()

dp = [[0] * (len(t) + 1) for _ in range(len(s) + 1)]
# 最長の文字数を求める
for i in range(len(s)):
    for j in range(len(t)):
        if s[i] == t[j]:
            dp[i + 1][j + 1] = dp[i][j] + 1
        dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j + 1], dp[i + 1][j])

# print(dp[-1][-1]) # 最長文字数
i, j = len(s), len(t)

ans = []
while i > 0 and j > 0:
    if s[i - 1] == t[j - 1] and dp[i][j] == dp[i - 1][j - 1] + 1:
        ans.append(s[i - 1])
        i -= 1
        j -= 1
    else:
        if dp[i - 1][j] == dp[i][j]:
            i -= 1
        else:
            j -= 1
print(*reversed(ans), sep='')

Buggy python submission (verdict: Time Limit Exceeded):
s = input()
t = input()

dp = [[0] * (len(t) + 1) for _ in range(len(s) + 1)]
# 最長の文字数を求める
for i in range(len(s)):
    for j in range(len(t)):
        if s[i] == t[j]:
            dp[i + 1][j + 1] = dp[i][j] + 1
        dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j + 1], dp[i + 1][j])

# print(dp[-1][-1]) # 最長文字数
i, j = len(s), len(t)

ans = []
while i > 0 and j > 0:
    if s[i - 1] == t[j - 1] and dp[i][j] == dp[i - 1][j - 1] + 1:
        ans.append(s[i - 1])
        i -= 1
        j -= 1
    else:
        if dp[i - 1][j] == dp[i][j]:
            i -= 1
        else:
            j -= 1
print(*reversed(ans), sep='')


Fixed submission:
s = input()
t = input()

dp = [[0] * (len(t) + 1) for _ in range(len(s) + 1)]
# 最長の文字数を求める
for i in range(len(s)):
    for j in range(len(t)):
        if s[i] == t[j]:
            dp[i + 1][j + 1] = dp[i][j] + 1
        dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j + 1], dp[i + 1][j])

# print(dp[-1][-1]) # 最長文字数
i, j = len(s), len(t)

ans = []
while i > 0 and j > 0:
    if s[i - 1] == t[j - 1] and dp[i][j] == dp[i - 1][j - 1] + 1:
        ans.append(s[i - 1])
        i -= 1
        j -= 1
    else:
        if dp[i - 1][j] == dp[i][j]:
            i -= 1
        else:
            j -= 1
print(*reversed(ans), sep='')
Buggy python submission (verdict: Runtime Error):

N, M = [int(_) for _ in input().split()]
E = [[] for _ in range(N)]

indegree = [0] * N  # 入次数
for i in range(M):
    a, b = [int(_) - 1 for _ in input().split()]
    E[a].append(b)
    indegree[b] += 1

sorted_nodes = []
dp = [0] * N


def rep(v):
    """初めて呼ばれたときに, そのノードからの最長ノード数を数えるイメージ"""
    if dp[v] != 0: return dp[v]
    for n in E[v]:
        dp[v] = max(dp[v], rep(n) + 1)
    return dp[v]

ans = 0
for i in range(N):
    ans = max(ans,rep(i))
print(ans)




Fixed submission:
from collections import deque

# deque
# https://docs.python.org/ja/3/library/collections.html#collections.deque
# pop(0), append が高速

# トポロジカルソート
# https://csacademy.com/lesson/topological_sorting/


N, M = [int(_) for _ in input().split()]
E = [[] for _ in range(N)]

indegree = [0] * N  # 入次数
for i in range(M):
    a, b = [int(_) - 1 for _ in input().split()]
    E[a].append(b)
    indegree[b] += 1

que = deque([i for i in range(N) if indegree[i] == 0])

sorted_nodes = []
dp = [0] * N
while que:
    n = que.popleft()
    sorted_nodes.append(n)
    for next_node in E[n]:
        indegree[next_node] = indegree[next_node] - 1  # 枝刈り
        if indegree[next_node] == 0:  # 入次数0なら queue に追加
            que.append(next_node)

        dp[next_node] = max(dp[next_node], dp[n] + 1)
# print(sorted_nodes)
print(max(dp))
Buggy python submission (verdict: Time Limit Exceeded):
N, M = list(map(int, input().split()))
ken = [[] for _ in range(N)]

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

for v in ken:
    v.sort()

for a, b in mlist:
    print("{:06d}{:06d}".format(a, ken[a - 1].index(b) + 1))


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

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

for v in ken:
    v.sort()


def search(v, lst):
    l, r = 0, len(lst) - 1
    while l <= r:
        m = (l + r) // 2
        if lst[m] == v:
            return m

        if lst[m] < v:
            l = m + 1
        else:
            r = m - 1
    return None


for a, b in mlist:
    print("{:06d}{:06d}".format(a, search(b,ken[a - 1]) + 1))
Buggy python submission (verdict: Runtime Error):
print(input().translate(str.maketrans({'1':'9','9':'1'}))

Fixed submission:
print(input().replace('1','x').replace('9','1').replace('x','9'))
Buggy python submission (verdict: Runtime Error):
from collections import Counter

N = int(input())
V = list(map(int, input().split()))

V1 = [V[i] for i in range(0, len(V), 2)]
V2 = [V[i] for i in range(1, len(V), 2)]

x = Counter(V1).most_common(2)
y = Counter(V2).most_common(2)
if x[0][1] < y[0][1]:
    x, y = y, x
elif x[0][1] == y[0][1] and x[1][1] > y[1][1]:
    x, y = y, x

l = int(N / 2)
res = l - x[0][1]
if y[0][0] == x[0][0]:
    res += l - (y[1][1] if len(y) > 1 else 0)
else:
    res += l - y[0][1]

print(res)


Fixed submission:
from collections import Counter

N = int(input())
V = list(map(int, input().split()))

V1 = [V[i] for i in range(0, len(V), 2)]
V2 = [V[i] for i in range(1, len(V), 2)]

x = Counter(V1).most_common(2)
y = Counter(V2).most_common(2)

if x[0][1] < y[0][1]:
    x, y = y, x
elif len(x)>1 and len(y) > 1 and x[0][1] == y[0][1] and x[1][1] > y[1][1]:
    x, y = y, x

l = int(N / 2)
res = l - x[0][1]
if y[0][0] == x[0][0]:
    res += l - (y[1][1] if len(y) > 1 else 0)
else:
    res += l - y[0][1]

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

N, X = list(map(int, input().split()))
xlist = list(map(int, input().split()))
xlist.append(X)
xlist.sort()

m = xlist[1] - xlist[0]
for i in range(1, len(xlist) - 1):
    d = xlist[i + 1] - xlist[i]
    m = math.gcd(d, m)
print(m)


Fixed submission:
def gcd(a, b):
    if b > a:
        a, b = b, a
    c = a % b
    if (c == 0):
        return b
    return gcd(b, c)


N, X = list(map(int, input().split()))
xlist = list(map(int, input().split()))
xlist.append(X)
xlist.sort()

m = xlist[1] - xlist[0]
for i in range(1, len(xlist) - 1):
    d = xlist[i + 1] - xlist[i]
    m = gcd(d, m)
print(m)
Buggy python submission (verdict: Time Limit Exceeded):
N, M = [int(v) for v in input().split()]
A = [int(v) for v in input().split()]
for i in range(1, N):
    A[i] += A[i - 1]

ans = 0
for l in range(N):
    for r in range(l, N):
        if l <= 0:
            lc = 0
        else:
            lc = A[l - 1]
        cnt = A[r] - lc
        if cnt % M == 0:
            ans += 1
print(ans)

Fixed submission:
N, M = [int(v) for v in input().split()]
A = [0] + [int(v) for v in input().split()]
for i in range(1, N + 1):
    A[i] = (A[i] + A[i - 1]) % M

from collections import Counter
import math


def combinations_count(n, r):
    if n <= 1:
        return 1
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


counter = Counter()
for a in A:
    counter[a] += 1

ans = 0
for c in counter.values():
    if c <= 1: continue
    ans += combinations_count(c, 2)
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = [int(_) for _ in input().split()]

A2 = [0] * (N + 1)

for i in range(1, N + 1):
    A2[i] = A2[i - 1] + A[i - 1]


def find(_l, _r):
    l, r = _l, _r
    lv, rv = A2[l - 1], A2[r]
    while l < r - 1:
        m = (r + l) // 2
        a = A2[m] - lv
        if a <= (rv - lv) / 2:
            l = m
        else:
            r = m
    if l < _r:
        if abs((A2[l] - lv) - (rv - A2[l])) > abs((A2[l + 1] - lv) - (rv - A2[l + 1])):
            return A2[l + 1] - lv, rv - A2[l + 1]
    return A2[l] - lv, rv - A2[l]


ans = 1e10
for i in range(2, N - 1):
    p, q = find(1, i)
    r, s = find(i + 1, N)
    # print(p, q, r, s)
    ans = min(ans, abs(max(p, q, r, s) - min(p, q, r, s)))
print(ans)


Fixed submission:
N = int(input())
A = [int(_) for _ in input().split()]

A2 = [0] * (N + 1)

for i in range(1, N + 1):
    A2[i] = A2[i - 1] + A[i - 1]


def find(_l, _r):
    l, r = _l, _r
    lv, rv = A2[l - 1], A2[r]
    while l < r - 1:
        m = (r + l) // 2
        a = A2[m] - lv
        if a <= (rv - lv) / 2:
            l = m
        else:
            r = m
    if l < _r:
        if abs((A2[l] - lv) - (rv - A2[l])) > abs((A2[l + 1] - lv) - (rv - A2[l + 1])):
            return A2[l + 1] - lv, rv - A2[l + 1]
    return A2[l] - lv, rv - A2[l]


ans = 1e10
for i in range(2, N - 1):
    p, q = find(1, i)
    r, s = find(i + 1, N)
    # print(p, q, r, s)
    ans = min(ans, abs(max(p, q, r, s) - min(p, q, r, s)))
print(ans)
Buggy python submission (verdict: Runtime Error):
import numpy  as np

N = int(input())

# log_6 10^5 < 7
# log_9 10^5 < 6
# 15 = 1 + 6 + 5
memo = np.zeros((15, N + 1))
memo[:, :] = N * 2
memo[0][0] = 0

values = []

i = 1
while i <= N:
    values.append(i)
    i *= 6
i = 9
while i <= N:
    values.append(i)
    i *= 9

for i in range(len(values)):
    v = values[i]
    for w in range(N+1):
        if v > w:
            memo[i + 1][w] = memo[i][w]
        else:
            memo[i + 1][w] = min(memo[i][w], memo[i+1][w - v] + 1)
print(int(memo[len(values)][N]))

Fixed submission:
import numpy  as np

N = int(input())

# log_6 10^5 < 7
# log_9 10^5 < 6
# 15 = 1 + 6 + 5
memo = np.zeros((15, N + 1),int)
memo[:, :] = N * 2
memo = memo.tolist()
memo[0][0] = 0

values = []

i = 1
while i <= N:
    values.append(i)
    i *= 6
i = 9
while i <= N:
    values.append(i)
    i *= 9

for i in range(len(values)):
    v = values[i]
    for w in range(N+1):
        if v > w:
            memo[i + 1][w] = memo[i][w]
        else:
            memo[i + 1][w] = min(memo[i][w], memo[i+1][w - v] + 1)
print(int(memo[len(values)][N]))

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

N = int(input())

# log_6 10^5 < 7
# log_9 10^5 < 6
# 15 = 1 + 6 + 5
memo = np.zeros((15, N + 1))
memo[:, :] = N * 2
memo[0][0] = 0

values = []

i = 1
while i <= N:
    values.append(i)
    i *= 6
i = 9
while i <= N:
    values.append(i)
    i *= 9

for i in range(len(values)):
    v = values[i]
    for w in range(N+1):
        if v > w:
            memo[i + 1][w] = memo[i][w]
        else:
            memo[i + 1][w] = min(memo[i][w], memo[i+1][w - v] + 1)
print(int(memo[len(values)][N]))

Fixed submission:
import numpy  as np

N = int(input())

# log_6 10^5 < 7
# log_9 10^5 < 6
# 15 = 1 + 6 + 5
memo = np.zeros((15, N + 1),int)
memo[:, :] = N * 2
memo = memo.tolist()
memo[0][0] = 0

values = []

i = 1
while i <= N:
    values.append(i)
    i *= 6
i = 9
while i <= N:
    values.append(i)
    i *= 9

for i in range(len(values)):
    v = values[i]
    for w in range(N+1):
        if v > w:
            memo[i + 1][w] = memo[i][w]
        else:
            memo[i + 1][w] = min(memo[i][w], memo[i+1][w - v] + 1)
print(int(memo[len(values)][N]))
Buggy python submission (verdict: Time Limit Exceeded):
s = input()
K = int(input())

cnt = 0
uni = set()
for i in range(1, len(s)+1):
    for j in range(len(s)):
        if len(s) - (j+i) < 0: break
        uni.add(s[j:j + i])

print(sorted(list(uni))[K-1])

Fixed submission:
s = input()
K = int(input())

cnt = 0
uni = set()
for i in range(1, K+1):
    for j in range(len(s)):
        if len(s) - (j+i) < 0: break
        uni.add(s[j:j + i])

print(sorted(list(uni))[K-1])
Buggy python submission (verdict: Time Limit Exceeded):
from collections import Counter


class Combination:
    def __init__(self, n):
        """

        :param n: 使用する最大のn (nCm)
        """
        self.n = n
        self.memo = [None for _ in range(n + 1)]
        self.memo[0] = [1]
        for i in range(1, n + 1):
            self._nCm_pascal(i)

    def _nCm_pascal(self, i):
        """
        パスカルの三角形のn階層目のリストを取得する
        :param i: 作成する階層
        :return:
        """
        if self.n < i:
            return

        pre_row = self.memo[i - 1]
        row = [1] * (i + 1)

        for j in range(1, i):
            row[j] = pre_row[j - 1] + pre_row[j]

        self.memo[i] = row

    def nCm(self, n, m):
        return self.memo[n][m]


N = [int(_) for _ in input().split()][0]
a = [int(_) for _ in input().split()]
s = [0] * (N + 1)

cnt = Counter()
comb = Combination(N)
for i in range(N):
    s[i + 1] = a[i] + s[i]
    cnt[s[i + 1]] += 1

ans = 0
for k, v in cnt.items():
    # print(k,v)
    if v <= 1: continue
    ans += comb.nCm(v, 2)
ans += cnt[0]
print(ans)


Fixed submission:
from collections import Counter

N = [int(_) for _ in input().split()][0]
a = [int(_) for _ in input().split()]

s = [0] * (len(a) + 1)
for i in range(len(a)):
    s[i + 1] = s[i] + a[i]

c = Counter()

for i in range(len(s)):
    c[s[i]] += 1

ans = 0
for cnt in c.values():
    if cnt < 2: continue

    ans += (cnt * (cnt - 1)) // 2
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
N = [int(_) for _ in input().split()][0]
a = [int(_) for _ in input().split()]

s = [0] * (len(a) + 1)
for i in range(len(a)):
    s[i + 1] = s[i] + a[i]

ans = 0
for l in range(len(a)):
    for r in range(l + 1, len(a) + 1):
        ans += s[r] - s[l] == 0
print(ans)



Fixed submission:
from collections import Counter

N = [int(_) for _ in input().split()][0]
a = [int(_) for _ in input().split()]

s = [0] * (len(a) + 1)
for i in range(len(a)):
    s[i + 1] = s[i] + a[i]

c = Counter()

for i in range(len(s)):
    c[s[i]] += 1

ans = 0
for cnt in c.values():
    if cnt < 2: continue

    ans += (cnt * (cnt - 1)) // 2
print(ans)