Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
from functools import reduce
from itertools import permutations
import sys
for n, s in (map(int, l.rstrip().split()) for l in sys.stdin):
    print(len([1 for a in permutations(range(10), n) if sum(i*n for i,n in enumerate(a, start=1))==s]))


Fixed submission:
from itertools import combinations
import sys

# dp[n][使った数字(bit)][合計] = count
dp = [[[0]*331 for _ in [0]*2048] for _ in [0]*11]
for i in range(11):
    dp[1][2**i][i] = 1

for i in range(2, 11):
    for used in (sum(comb) for comb in combinations([2**n for n in range(10)], i-1)):
        for j in filter(lambda x: used & 2**x == 0, range(10)):
            for total, count in filter(lambda p: p[1]>0, enumerate(dp[i-1][used])):
                dp[i][used|2**j][total+j*i] += count

for n, s in (map(int, l.rstrip().split()) for l in sys.stdin):
    print(sum(a[s] for a in dp[n] if a[s]) if s<331 else 0)

Buggy python submission (verdict: Runtime Error):
from itertools import combinations
import sys

# dp[n][使った数字(bit)][合計] = count
dp = [[[0]*331 for _ in [0]*2048] for _ in [0]*11]
for i in range(11):
    dp[1][2**i][i] = 1

for i in range(2, 11):
    for used in (sum(comb) for comb in combinations([2**n for n in range(10)], i-1)):
        for j in filter(lambda x: used & 2**x == 0, range(10)):
            for total, count in filter(lambda p: p[1]>0, enumerate(dp[i-1][used])):
                dp[i][used|2**j][total+j*i] += count

for n, s in (map(int, l.rstrip().split()) for l in sys.stdin):
    print(sum(a[s] for a in dp[n] if a[s]))


Fixed submission:
from itertools import combinations
import sys

# dp[n][使った数字(bit)][合計] = count
dp = [[[0]*331 for _ in [0]*2048] for _ in [0]*11]
for i in range(11):
    dp[1][2**i][i] = 1

for i in range(2, 11):
    for used in (sum(comb) for comb in combinations([2**n for n in range(10)], i-1)):
        for j in filter(lambda x: used & 2**x == 0, range(10)):
            for total, count in filter(lambda p: p[1]>0, enumerate(dp[i-1][used])):
                dp[i][used|2**j][total+j*i] += count

for n, s in (map(int, l.rstrip().split()) for l in sys.stdin):
    print(sum(a[s] for a in dp[n] if a[s]) if s<331 else 0)
Buggy python submission (verdict: Time Limit Exceeded):
import math

class SegmentTree(object):
    __slots__ = ["elem_size", "tree", "default", "op"]

    def __init__(self, a: list, default: int, op):
        real_size = len(a)
        self.elem_size = elem_size = 1 << math.ceil(math.log2(real_size))
        self.tree = tree = [default] * (elem_size * 2)
        tree[elem_size:elem_size+real_size] = a
        self.default = default
        self.op = op

        for i in range(elem_size - 1, 0, -1):
            tree[i] = op(tree[i<<1], tree[(i<<1)+1])

    def get_value(self, x: int, y: int) -> int:
        l, r = x + self.elem_size, y + self.elem_size
        tree, result, op = self.tree, self.default, self.op
        while l < r:
            if l & 1:
                result = op(tree[l], result)
                l += 1
            if r & 1:
                r -= 1
                result = op(tree[r], result)
            l, r = l >> 1, r >> 1

        return result

    def set_value(self, i: int, value: int) -> None:
        k = self.elem_size + i
        self.tree[k] = value
        self.update(k)

    def update(self, i: int) -> None:
        op, tree = self.op, self.tree
        while i > 1:
            i >>= 1
            tree[i] = op(tree[i<<1], tree[(i<<1) + 1])

if __name__ == "__main__":
    import sys
    from bisect import bisect_right

    N, d = map(int, sys.stdin.readline().split())
    b_l, x_l, y_l = zip(*sorted([(b, x, y) for l in sys.stdin.readlines() for x, y, b in (map(int, l.split()),)]))
    inf, minf = float("inf"), float("-inf")
    x_min = SegmentTree(x_l, inf, min)
    x_max = SegmentTree(x_l, minf, max)
    y_min = SegmentTree(y_l, inf, min)
    y_max = SegmentTree(y_l, minf, max)

    ans = 0
    for l, (b, _) in enumerate(zip(b_l, [-1]+list(b_l))):
        if b == _:
            continue
        r = bisect_right(b_l, b+d)
        x1, x2 = x_min.get_value(l, r), x_max.get_value(l, r)
        y1, y2 = y_min.get_value(l, r), y_max.get_value(l, r)
        ans = max(ans, (x2-x1)*(y2-y1))
    print(ans)



Fixed submission:
import sys
from heapq import heappop, heappush
from operator import itemgetter

N, d = map(int, sys.stdin.readline().split())
x_max, x_min, y_max, y_min = [], [], [], []

ans = 0
for x, y, b in sorted([list(map(int, l.split())) for l in sys.stdin.readlines()], key=itemgetter(2)):
    heappush(x_max, (-x, b))
    heappush(x_min, (x, b))
    heappush(y_max, (-y, b))
    heappush(y_min, (y, b))
    for _a in (x_max, x_min, y_max, y_min):
        while _a[0][1] < b-d:
            heappop(_a)

    area = (-x_max[0][0]-x_min[0][0])*(-y_max[0][0]-y_min[0][0])
    if area > ans:
        ans = area
print(ans)
Buggy python submission (verdict: Runtime Error):
def solve():
    N, K = map(int, input().split())
    a = [[] for _ in [0]*10]
    l = []
    for c, g in (tuple(map(int, input().split())) for _ in [0]*N):
        a[g-1].append(c)

    for i, prices in enumerate(a):
        ln = len(prices)
        if ln == 0:
            continue
        dp = [[-1]*(K+1) for _ in [0]*(ln+1)]
        dp[0][0] = 0
        for j, price in enumerate(prices):
            for k, prev in enumerate(dp[j][:j+1]):
                if prev > dp[j+1][k]:
                    dp[j+1][k] = prev
                if prev+price+k*2 > dp[j+1][k+1]:
                    dp[j+1][k+1] = prev+price+k*2
        l.append(dp[-1][1:ln+1])

    dp = [0]*(K+1)
    for prices in l:
        for i, price in enumerate(prices, start=1):
            for j, cur, prev in zip(range(K, -1, -1), dp[::-1], dp[K-i::-1]):
                if prev+price > cur:
                    dp[j] = prev+price

    print(max(dp))
    

if __name__ == "__main__":
    solve()

Fixed submission:
def solve():
    N, K = map(int, input().split())
    a = [[] for _ in [0]*10]
    l = []
    for c, g in (tuple(map(int, input().split())) for _ in [0]*N):
        a[g-1].append(c)

    for i, prices in enumerate(a):
        ln = len(prices)
        if ln == 0:
            continue
        dp = [0]*(K+1)
        for j, price in enumerate(prices):
            _k = j if j < K-1 else K-1
            for k, prev, cur in zip(range(_k, -1, -1), dp[_k::-1], dp[_k+1::-1]):
                if prev+price+k*2 > cur:
                    dp[k+1] = prev+price+k*2
        l.append(dp[1:ln+1])

    dp = [float("-inf")]*(K+1)
    dp[0] = 0
    for prices in l:
        cdp = dp[:]
        for i, price in enumerate(prices, start=1):
            if i > K:
                break
            for j, cur, prev in zip(range(K, -1, -1), cdp[::-1], dp[K-i::-1]):
                if 0 < prev+price > cur:
                    cdp[j] = prev+price
        dp = cdp

    print(max(dp))


if __name__ == "__main__":
    solve()
Buggy python submission (verdict: Runtime Error):
def solve():
    A, B = map(int, input().split())
    s1 = tuple(map(int, input().split()))
    s2 = tuple(map(int, input().split()))
    result = 0

    for i in range(B):
        k = 0
        cnt = 0
        for j, n in enumerate(s2[i:]):
            while k < A and n != s1[k]:
                k += 1
            if n == s1[k]:
                cnt += 1
            if k == A:
                break
        if cnt > result:
            result = cnt

    print(result)


if __name__ == "__main__":
    solve()

Fixed submission:
def solve():
    A, B = map(int, input().split())
    s1 = tuple(map(int, input().split()))
    s2 = tuple(map(int, input().split()))
    set1 = [0]*(A+1)
    set1[-1] = set()
    for i, n in enumerate(s1[::-1], start=2):
        set1[-i] = set1[-i+1] | {n}
    result = 0

    for i in range(B):
        k = 0
        cnt = 0
        for n in s2[i:]:
            if n not in set1[k]:
                break
            for m in s1[k:]:
                k += 1
                if n == m:
                    cnt += 1
                    break
        if cnt > result:
            result = cnt
        if result >= B-i:
            break
    print(result)


if __name__ == "__main__":
    solve()
Buggy python submission (verdict: Runtime Error):
import sys
from operator import itemgetter
from itertools import permutations

def solve(a: list):
    length = len(a)
    if length <= 3:
        return min((p1[0]-p2[0])**2+(p1[1]-p2[1])**2 for p1, p2 in permutations(a, 2))

    x_set_len = len(set(x for (x, _) in a))
    axis = 0 if x_set_len > length/2 else 1
    a.sort(key=itemgetter(axis))
    mid_index = length//2
    left, right = a[:mid_index], a[mid_index:]
    delta = min(solve(left), solve(right))
    median = a[mid_index][axis]
    m_a = []
    append = m_a.append
        
    for p in left[::-1]:
        if p[axis] < median-delta:
            break
        append(p)
    for p in right:
        if p[axis] > median+delta:
            break
        append(p)
    m_a.sort(key=itemgetter(not axis))

    for i, p1 in enumerate(m_a):
        ub = p1[not axis] + delta
        for j, p2 in enumerate(m_a[i+1:]):
            if p2[not axis] > ub:
                break
            delta = min(delta, (p1[0]-p2[0])**2+(p1[1]-p2[1])**2)

    return delta

if __name__ == "__main__":
    N = int(input())
    a = [tuple(map(int, l.split())) for l in sys.stdin.readlines()]
    print(solve(a))


Fixed submission:
import sys
from operator import itemgetter
from itertools import combinations, takewhile
from math import sqrt

def solve(a: list, sorted_axis: int = -1):
    length = len(a)
    if length <= 3:
        return min((x1-x2)**2+(y1-y2)**2 for (x1, y1), (x2, y2) in combinations(a, 2))

    x_set_len = len(set(x for x, _ in a))
    axis1 = 0 if x_set_len > length/2 else 1

    if sorted_axis != axis1:
        a.sort(key=itemgetter(axis1))

    mid_index = length//2
    left, right = a[:mid_index], a[mid_index:]
    delta = min(solve(left, axis1), solve(right, axis1))

    axis2 = not axis1
    median = a[mid_index][axis1]
    mid_a = sorted([p for _iter in (
        (takewhile(lambda p: median-sqrt(delta) < p[axis1], left[::-1])),
        (takewhile(lambda p: p[axis1] < median+sqrt(delta), right))
    ) for p in _iter], key=itemgetter(axis2))

    for i, (x1, y1) in enumerate(mid_a):
        ub = (x1 if axis1 else y1) + sqrt(delta)
        for x2, y2 in takewhile(lambda p: p[axis2] < ub, mid_a[i+1:]):
            delta = min(delta, (x1-x2)**2+(y1-y2)**2)

    return delta

if __name__ == "__main__":
    N = int(input())
    a = [tuple(map(int, l.split())) for l in sys.stdin.readlines()]
    print(solve(a))
Buggy python submission (verdict: Time Limit Exceeded):
q = int(input())
for _ in [0]*q:
    s1, s2 = input(), input()
    l1, l2 = len(s1), len(s2)

    dp = [[0]*(l2+1) for _ in [0]*(l1+1)]
    for i, c1 in enumerate(s1, start=1):
        for j, c2 in enumerate(s2, start=1):
            dp[i][j] = max(dp[i][j], dp[i-1][j], dp[i][j-1], dp[i-1][j-1]+(c1==c2))

    print(dp[-1][-1])


Fixed submission:
def lcs_hs(s1, s2):
    from bisect import bisect_left

    s2, lis, result = s2[::-1], [], 0
    find, append = s2.find, lis.append

    for c in s1:
        i = find(c)+1
        while i:
            j = bisect_left(lis, -i)
            if j >= result:
                append(-i)
                result += 1
            else:
                lis[j] = -i
            i = find(c, i)+1

    return result


print(*(lcs_hs(input(), input()) for _ in [0]*int(input())), sep="\n")

Buggy python submission (verdict: Time Limit Exceeded):
q = int(input())
for _ in [0]*q:
    s1, s2 = input(), input()
    l1, l2 = len(s1), len(s2)

    dp = [[0]*(l2+1) for _ in [0]*(l1+1)]
    for i, (c1, prev, cur) in enumerate(zip(s1, dp, dp[1:]), start=1):
        for j, (c2, ul, u, l, c) in enumerate(zip(s2, prev, prev[1:], cur, cur[1:]), start=1):
            dp[i][j] = max(ul+(c1==c2), u, l, c)

    print(dp[-1][-1])


Fixed submission:
def lcs_hs(s1, s2):
    from bisect import bisect_left

    s2, lis, result = s2[::-1], [], 0
    find, append = s2.find, lis.append

    for c in s1:
        i = find(c)+1
        while i:
            j = bisect_left(lis, -i)
            if j >= result:
                append(-i)
                result += 1
            else:
                lis[j] = -i
            i = find(c, i)+1

    return result


print(*(lcs_hs(input(), input()) for _ in [0]*int(input())), sep="\n")
Buggy python submission (verdict: Time Limit Exceeded):
import sys
import math
def get_prime(m):
    a = [2]+[i for i in range(3,m+1,2)]
    end = int(math.sqrt(m))
    for i in range(3, end, 2):
        if (i in a):
            for j in range(i*2, m, i):
                if (j in a):
                    a.remove(j)
            
    return a
n = int(input())
a = []
for i in range(n):
    a.append(int(input()))
primes = get_prime(max(a))
result = 0
for i in range(n):
    if a[i] in primes:
        result+=1
print(result)

Fixed submission:
import math
n = int(input())
cnt = 0
for i in range(n):
    num = int(input())
    flag = True
    for j in range(2, int(math.sqrt(num))+1):
        if num%j == 0:
            flag = False
            break
    if flag:
        cnt+=1
print(cnt)
Buggy python submission (verdict: Runtime Error):
from collections import deque
dq = deque()
for _ in [None]*int(input()):
    s = input()
    if s == "deleteFirst":
        dq.popleft()
    elif s == "deleteLast":
        dq.pop()
    else:
        a, b = s.split()
        if a == "insert":
            dq.insert(0, b)
        else:
            dq.remove(b)
print(" ".join(dq))

Fixed submission:
from collections import deque
dq = deque()
for _ in [None]*int(input()):
    s = input()
    if s == "deleteFirst":
        dq.popleft()
    elif s == "deleteLast":
        dq.pop()
    else:
        a, b = s.split()
        if a == "insert":
            dq.appendleft(b)
        else:
            if b in dq:
                dq.remove(b)
print(" ".join(dq))

Buggy python submission (verdict: Runtime Error):
from collections import deque
dq = deque()
for _ in [None]*int(input()):
    s = input()
    if s == "deleteFirst":
        dq.popleft()
    elif s == "deleteLast":
        dq.pop()
    else:
        a, b = s.split()
        if a == "insert":
            dq.appendleft(b)
        else:
            dq.remove(b)
print(" ".join(dq))

Fixed submission:
from collections import deque
dq = deque()
for _ in [None]*int(input()):
    s = input()
    if s == "deleteFirst":
        dq.popleft()
    elif s == "deleteLast":
        dq.pop()
    else:
        a, b = s.split()
        if a == "insert":
            dq.appendleft(b)
        else:
            if b in dq:
                dq.remove(b)
print(" ".join(dq))
Buggy python submission (verdict: Time Limit Exceeded):
import bisect
n = int(input())
S = tuple(map(int, input().split()))
q = int(input())
T = tuple(map(int, input().split()))
cnt = 0
for n in T:
    cnt += n in S
print(cnt)

Fixed submission:
import bisect
n = int(input())
S = tuple(map(int, input().split()))
q = int(input())
T = tuple(map(int, input().split()))
cnt = 0
for n in T:
    m = bisect.bisect_right(S, n)
    if m > 0 and S[m-1] == n:
        cnt += 1
print(cnt)
Buggy python submission (verdict: Runtime Error):
    N, W = map(int, input().split())
    dp = [0] + [-1]*(W+1)
    for i in range(N):
        v, w = map(int, input().split())
        for j in range(0, W-w+1):
            if dp[j] > -1 and dp[j+w] < dp[j] + v:
                dp[j+w] = dp[j] + v

    print(max(dp))

Fixed submission:
N, W = map(int, input().split())
dp = [0] + [-1]*(W+1)
for i in range(N):
    v, w = map(int, input().split())
    for j in range(0, W-w+1):
        if dp[j] > -1 and dp[j+w] < dp[j] + v:
            dp[j+w] = dp[j] + v

print(max(dp))
Buggy python submission (verdict: Time Limit Exceeded):
s1 = input()
s2 = input()
if len(s1) < len(s2):
    s1, s2 = s2, s1
length = len(s2)
dp = {(s1, 0): 0}
result = float("inf")

while dp:
    hoge = []
    append = hoge.append
    for key, n in dp.items():
        #print(key, n)
        s, i = key
        if s == s2:
            result = n if n < result else result
        elif length <= i:
            append((s[:-1], i, n+1))
        elif len(s) == i:
            append((s+s2[i], i+1, n+1))
        elif s[i] == s2[i]:
            append((s, i+1, n))
        else:
            s_mod1 = s[:i] + s2[i] + s[i+1:]
            s_mod2 = s[:i] + s[i+1:]
            s_mod3 = s[:i] + s2[i] + s[i:]
            append((s_mod1, i+1, n+1))
            append((s_mod2, i, n+1))
            append((s_mod3, i+1, n+1))
    dp = dict()
    for a, b, c in hoge:
        key = (a, b)
        if key not in dp or dp[key] > c:
            dp[key] = c
    #print(dp)
print(result)

Fixed submission:
s1 = input()
s2 = input()


def levenshtein(s1, s2):
    s1_len = len(s1)
    prev = range(s1_len+1)
    current = None

    for i, c1 in enumerate(s2, start=1):
        current = [i] * (s1_len+1)
        for j, c2 in enumerate(s1, start=1):
            n1 = prev[j-1] if c1 == c2 else prev[j-1]+1
            n2 = prev[j]+1
            n3 = current[j-1]+1
            current[j] = min(n1, n2, n3)
        prev = current

    return current[-1]

print(levenshtein(s1, s2))
Buggy python submission (verdict: Time Limit Exceeded):
def solve():
    from heapq import heappop, heappush
    V, E = map(int, input().split())
    edges = [[] for _ in [0]*V]
    for _ in [0]*E:
        s, t, d = map(int, input().split())
        edges[s].append((t, d))

    result = float("inf")
    for i in range(V):
        q = [(0, i, {i})]
        while q:
            cost, v, visited = heappop(q)
            if len(visited) < V:
                for dest, d_cost in edges[v]:
                    if dest not in visited:
                        heappush(q, (cost+d_cost, dest, visited | {dest}))
            elif len(visited) == V:
                for dest, d_cost in edges[v]:
                    if dest == i:
                        heappush(q, (cost+d_cost, i, visited | {-1}))
            else:
                if result > cost:
                    result = cost
                break

    print(result if result < float("inf") else -1)


if __name__ == "__main__":
    solve()

Fixed submission:
def solve():
    V, E = map(int, input().split())
    edges = [[] for _ in [0]*V]
    for _ in [0]*E:
        s, t, d = map(int, input().split())
        edges[s].append((t, d))

    result = float("inf")
    beam_width = 66
    for i in range(V):
        q = [(0, i, {i})]
        for j in range(V-1):
            _q = []
            append = _q.append
            for cost, v, visited in q[:beam_width+1]:
                for dest, d_cost in edges[v]:
                    if dest not in visited:
                        append((cost+d_cost, dest, visited | {dest}))
            q = sorted(_q)
        for cost, v, visited in q[:beam_width+1]:
            for dest, d_cost in edges[v]:
                if dest == i:
                    if result > cost + d_cost:
                        result = cost + d_cost
                        break

    print(result if result < float("inf") else -1)


if __name__ == "__main__":
    solve()
Buggy python submission (verdict: Runtime Error):
import sys


class BinaryIndexedTree(object):
    __slots__ = ["tree"]

    def __init__(self, size: int):
        self.tree = [0]*(size+1)

    def add(self, index: int, value: int) -> None:
        tree = self.tree
        next_index = index + 1

        while next_index < len(tree):
            tree[next_index] += value
            next_index += next_index & -next_index

    def sum(self, index: int):
        tree, result = self.tree, 0
        next_index = index + 1

        while next_index:
            result += tree[next_index]
            next_index -= next_index & -next_index

        return result


if __name__ == "__main__":
    n, q = map(int, input().split())
    bit = BinaryIndexedTree(n)
    result = []
    for com, x, y in (map(int, l.split()) for l in sys.stdin):
        if not com:
            bit.add(x, y)
        else:
            result.append(bit.sum(y) - bit.sum(x-1))

    print(*result, sep="\n")


Fixed submission:
import math


class SegmentTree:
    __slots__ = ["elem_size", "tree_size", "tree"]

    def __init__(self, a: list, default: int):
        real_size = len(a)
        self.elem_size = 1 << math.ceil(math.log2(real_size))
        self.tree_size = 2 * self.elem_size + 1
        self.tree = [default] * (self.elem_size - 1) + a + [default] * (self.elem_size - real_size)

    def get_range_index(self, x, y, k=0, l_end=0, r_end=None):
        '''[x, y], tree[k], [l_end, r_end)'''
        default, tree = 0, self.tree
        if r_end is None:
            r_end = self.elem_size

        if l_end == x and y == r_end-1:
            return tree[k]

        mid = (l_end + r_end) // 2
        left_y = y if y < mid-1 else mid-1
        right_x = x if x > mid else mid

        left = self.get_range_index(x, left_y, 2*k+1, l_end, mid) if x <= left_y else default
        right = self.get_range_index(right_x, y, 2*k+2, mid, r_end) if right_x <= y else default
        return left + right

    def get_value(self, x, y):
        tree = self.tree
        return self.get_range_index(x, y)

        # return sum(tree[n] for n in index_list)

    def update_tree(self, k: int):
        tree = self.tree

        while k > 0:
            k = (k-1) // 2
            left, right = tree[2*k+1], tree[2*k+2]
            tree[k] = left + right

    def set_value(self, i: int, value: int, op: str):
        k = self.elem_size - 1 + i
        if op == "=":
            self.tree[k] = value
        elif op == "+":
            self.tree[k] += value
        self.update_tree(k)


n, q = map(int, input().split())
rsq = SegmentTree([0]*n, 0)
ans = []
for _ in [0]*q:
    c, x, y = map(int, input().split())
    if c == 0:
        rsq.set_value(x-1, y, "+")
    else:
        ans.append(rsq.get_value(x-1, y-1))
print("\n".join([str(n) for n in ans]))
Buggy python submission (verdict: Runtime Error):
import numpy as np
import math
n = int(input())
a = np.array([int(n) for n in input().split()])
divisors = []
for i in range(2, math.ceil(math.sqrt(a.max()))+1):
    while True:
        cond = (a%i==0)
        if cond.sum() > 1:
            a[cond] //= i
            divisors.append(i)
        else:
            break
print(int(np.concatenate((a,divisors)).cumprod()[-1]))

Fixed submission:
n = int(input())
a = map(int, input().split())
result = a.__next__()

for nb in a:
    na = result
    result *= nb
    while nb > 0:
        na, nb = nb, na%nb
    result //= na

print(result)

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

Fixed submission:
n = int(input())
a = map(int, input().split())
result = a.__next__()

for nb in a:
    na = result
    result *= nb
    while nb > 0:
        na, nb = nb, na%nb
    result //= na

print(result)