Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
n,k = map(int, input().split())

ret = []

for i in range(n):
    a,b = map(int, input().split())
    ret += [a] * b

ret.sort()

print(ret[k-1])


Fixed submission:
n,k = map(int, input().split())

ret = {}

for i in range(n):
    a,b = map(int, input().split())
    ret[a] = ret.get(a, 0) + b

for i in sorted(ret.keys()):
    k -= ret[i]
    if k <= 0:
        print(i)
        break
Buggy python submission (verdict: Runtime Error):
N = int(input())
v = [list(map(input().split)) for i in range(N)]
v.sort(key = lambda x:abs(x[0]) + abs(x[1]))
d = abs(v[0][0] - v[N-1][0]) + abs(v[0][1] - v[N-1][1])
print(d)


Fixed submission:
N = int(input())
v = [list(map(int, input().split())) for i in range(N)]
minx = min([v[i][0] for i in range(N)])
miny = min([v[i][1] for i in range(N)])
v.sort(key = lambda x:x[0] - minx + x[1] - miny)
d = abs(v[0][0] - v[N-1][0]) + abs(v[0][1] - v[N-1][1])
result = d
v.sort(key = lambda x:x[0] - minx - (x[1] - miny))
d = abs(v[0][0] - v[N-1][0]) + abs(v[0][1] - v[N-1][1])
print(max(d, result))
Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np
from numba import njit
def main():
    N = int(input())
    nlist = np.array(list(map(int, input().split())))

    def gdc(x, y):
        b = max(x, y)
        s = min(x, y)
        r = b % s
        if r == 0:
            return s
        else:
            return gdc(s, r)

    scp = False
    pcp = False

    sgdc = nlist[0]
    for n in nlist:
        sgdc = gdc(sgdc, n)
        if sgdc == 1:
            scp = True

    if not scp:
        print('not coprime')
        exit()

    pcheckl = np.full((10**6+1), 0)
    for n in nlist:
        pcheckl[n] = 1

    pcp = np.all([sum(pcheckl[i::i]) <= 1 for i in range(2, 10**6+1)])

    if pcp:
        print('pairwise coprime')
    elif scp:
        print('setwise coprime')

if __name__ == '__main__':
    main()

Fixed submission:
import numpy as np
from numba import njit
def main():
    N = int(input())
    nlist = np.array(list(map(int, input().split())))

    def gdc(x, y):
        b = max(x, y)
        s = min(x, y)
        r = b % s
        if r == 0:
            return s
        else:
            return gdc(s, r)

    scp = False
    pcp = False

    sgdc = nlist[0]
    for n in nlist:
        sgdc = gdc(sgdc, n)
        if sgdc == 1:
            scp = True

    if not scp:
        print('not coprime')
        exit()

    pcheckl = [0] * (10**6+1)
    for n in nlist:
        pcheckl[n] = 1

    pcp = all([sum(pcheckl[i::i]) <= 1 for i in range(2, 10**6+1)])

    if pcp:
        print('pairwise coprime')
    elif scp:
        print('setwise coprime')

if __name__ == '__main__':
    main()
Buggy python submission (verdict: Runtime Error):
N=input()
print('YES' if N%9==0 else 'NO')

Fixed submission:
N = input()
sum = 0
for c in N:
    sum += int(c)
if sum % 9 == 0:
    print('Yes')
else:
    print('No')
Buggy python submission (verdict: Time Limit Exceeded):
'''
dpt[r][c][taken]
への遷移は、
max(dpt[r-1][c]) -> dpt[r][c][0]
dpt[r][c-1][taken-1] -> dpt[r][c][taken] + field[r][c]
dpt[r][c-1][taken] -> dpt[r][c][taken]
'''

import numpy as np
from numba import njit
def main():
    R, C, K = map(int, input().split())
    field = np.full((R+1,C+1), 0)
    dpt = np.full((R+1,C+1,4), 0)
    for i in range(K):
        r, c, v = map(int, input().split())
        field[r][c] = v
    dp(R, C, field, dpt)
    print(max(dpt[-1][-1]))

def dp(R, C, field, dpt):
    for r in range(1, R+1):
        for c in range(1, C+1):
            for taken in range(4):
                max_v = 0
                if taken == 0:
                    max_v = max(dpt[r-1][c])
                    max_v = max(dpt[r][c-1][0], max_v)
                elif taken == 1:
                    max_v = max(dpt[r][c-1][taken-1] + field[r][c],
                                dpt[r][c-1][taken],
                                max(dpt[r-1][c]) + field[r][c])
                else:
                    max_v = max(dpt[r][c-1][taken-1] + field[r][c],
                                dpt[r][c-1][taken])
                dpt[r][c][taken] = max_v
    return True

if __name__ == '__main__':
    main()


Fixed submission:
import numpy as np
from numba import njit
def main():
    R, C, K = map(int, input().split())
    field = np.full((R+1,C+1), 0, dtype='int64')
    dpt = np.full((R+1,C+1,4), 0, dtype='int64')
    for i in range(K):
        r, c, v = map(int, input().split())
        field[r][c] = v
    dp(R, C, field, dpt)
    print(max(dpt[-1][-1]))

@njit('i4(i4,i4,i8[:,:],i8[:,:,:])', cache=True)
def dp(R, C, field, dpt):
    for r in range(1, R+1):
        for c in range(1, C+1):
            for taken in range(4):
                max_v = 0
                if taken == 0:
                    max_v = max(dpt[r-1][c])
                    max_v = max(dpt[r][c-1][0], max_v)
                elif taken == 1:
                    max_v = max(dpt[r][c-1][taken-1] + field[r][c],
                                dpt[r][c-1][taken],
                                max(dpt[r-1][c]) + field[r][c])
                else:
                    max_v = max(dpt[r][c-1][taken-1] + field[r][c],
                                dpt[r][c-1][taken])
                dpt[r][c][taken] = max_v
    return 1

if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
K = int(input())
if K % 2 == 0:
    print(-1)
else:
    r = 0
    rem = 7
    while (True):
        r += 1
        rem = rem % K
        if rem == 0:
            break
        rem = (rem * 10) + 7
    print(r)


Fixed submission:
K = int(input())
if K % 2 == 0:
    print(-1)
else:
    r = 0
    rem = 7
    while (True):
        r += 1
        rem = rem % K
        if rem == 0:
            break
        if r > K:
            r = -1
            break
        rem = (rem * 10) + 7
    print(r)

Buggy python submission (verdict: Runtime Error):
K = int(input())
if K % 2 == 0:
    print(-1)
else:
    r = 1
    x = 7
    while True:
        if x % K == 0:
            break
        r += 1
        x = (x*10+7) % K
print(r)


Fixed submission:
K = int(input())
if K % 2 == 0:
    print(-1)
else:
    r = 0
    rem = 7
    while (True):
        r += 1
        rem = rem % K
        if rem == 0:
            break
        if r > K:
            r = -1
            break
        rem = (rem * 10) + 7
    print(r)
Buggy python submission (verdict: Time Limit Exceeded):
import heapq
import math

length_heap = []

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

length_list = list(map(int, input().split()))
for index, l in enumerate(length_list):
    heapq.heappush(length_heap, (-l, 1, index))

for i in range(total_cut):
    longest, cut_n, idx = heapq.heappop(length_heap)
    heapq.heappush(length_heap, (-length_list[idx]/(cut_n+1), (cut_n + 1), idx))

result = -heapq.heappop(length_heap)[0]

print(math.ceil(result))


Fixed submission:
import math
N, K = map(int, input().split())

log_list = list(map(int, input().split()))

maxx = 10**9
minx = 0

while (maxx - minx != 1):
    midx = (maxx + minx) // 2
    cut_n = sum([math.ceil(length / midx)-1 for length in log_list])
    if cut_n > K:
        minx = midx
    else:
        maxx = midx


print(maxx)
Buggy python submission (verdict: Runtime Error):
n = 10000
ans = {}
for x in range(1, 100):
    for y in range(1, 100):
        for z in range(1, 100):
            i = x**2 + y**2 + z**2 + x*y + y*z + z*x
                ans.setdefault(i, 0)
                ans[i] += 1
for i in range(1, N+1):
    print(ans[i])


Fixed submission:
N = int(input())
ans = {i:0 for i in range(100000)}
for x in range(1, 100):
    for y in range(1, 100):
        for z in range(1, 100):
            i = x**2 + y**2 + z**2 + x*y + y*z + z*x
            ans[i] += 1
for i in range(1, N+1):
    print(ans[i])
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
n_list = list(map(int, input().split()))
q = int(input())

n_dic = {}
for i in n_list:
    n_dic.setdefault(i, 0)
    n_dic[i] += 1

for i in range(q):
    b, c = map(int, input().split())
    if b in n_dic:
        n_dic.setdefault(c, 0)
        n_dic[c] += n_dic[b]
        del n_dic[b]

    result = 0
    for k in n_dic:
        result += k * n_dic[k]
    print(result)


Fixed submission:
n = int(input())
n_list = list(map(int, input().split()))
q = int(input())

n_dic = {}
for i in n_list:
    n_dic.setdefault(i, 0)
    n_dic[i] += 1

result = 0
for k in n_dic:
    result += k * n_dic[k]

for i in range(q):
    b, c = map(int, input().split())
    if b in n_dic:
        n_dic.setdefault(c, 0)
        n_dic[c] += n_dic[b]
        result = result + (c-b)*n_dic[b]
        del n_dic[b]

    print(result)

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
n_list = list(map(int, input().split()))
q = int(input())

for i in range(q):
    b, c = map(int, input().split())
    n_list = [i if i != b else c for i in n_list]
    print(sum(n_list))



Fixed submission:
n = int(input())
n_list = list(map(int, input().split()))
q = int(input())

n_dic = {}
for i in n_list:
    n_dic.setdefault(i, 0)
    n_dic[i] += 1

result = 0
for k in n_dic:
    result += k * n_dic[k]

for i in range(q):
    b, c = map(int, input().split())
    if b in n_dic:
        n_dic.setdefault(c, 0)
        n_dic[c] += n_dic[b]
        result = result + (c-b)*n_dic[b]
        del n_dic[b]

    print(result)
Buggy python submission (verdict: Runtime Error):
s = input()
if s == 'Sunny':
    result = 'Cloudy'
elif s == 'Cloudy':
    result = 'Rainy':
else:
    result = 'Sunny'

print(result)


Fixed submission:
s = input()
if s == 'Sunny':
    result = 'Cloudy'
elif s == 'Cloudy':
    result = 'Rainy'
else:
    result = 'Sunny'

print(result)
Buggy python submission (verdict: Time Limit Exceeded):
import heapq

def main():
    N, M = map(int, input().split())

    n_list = list(map(int, input().split()))
    heapq.heapify(n_list)

    for i in range(M):
        b, c = map(int, input().split())
        for i in range(b):
            n = heapq.heappop(n_list)
            if c > n:
                heapq.heappush(n_list, c)
            else:
                heapq.heappush(n_list, n)
                break

    print(sum(n_list))

if __name__ == '__main__':
    main()


Fixed submission:
import heapq

def main():
    N, M = map(int, input().split())
    n_list = map(int, input().split())
    n_dic = {}
    for n in n_list:
        n_dic.setdefault(n, 0)
        n_dic[n] += 1
    
    for i in range(M):
        b, c = map(int, input().split())
        n_dic.setdefault(c, 0)
        n_dic[c] += b
    
    com_list = []

    for score, num in n_dic.items():
        heapq.heappush(com_list, (-score, num))
    
    taken = 0
    result = 0

    while True:
        score, num = heapq.heappop(com_list)
        score = -score
        if N - taken > num:
            result += score * num
            taken += num
        else:
            result += score * (N - taken)
            break
    
    print(result)

main()

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

n_list = list(map(int, input().split()))
heapq.heapify(n_list)

for i in range(M):
    b, c = map(int, input().split())
    for i in range(b):
        n = heapq.heappop(n_list)
        if c > n:
            heapq.heappush(n_list, c)
        else:
            heapq.heappush(n_list, n)
            break

print(sum(n_list))



Fixed submission:
import heapq

def main():
    N, M = map(int, input().split())
    n_list = map(int, input().split())
    n_dic = {}
    for n in n_list:
        n_dic.setdefault(n, 0)
        n_dic[n] += 1
    
    for i in range(M):
        b, c = map(int, input().split())
        n_dic.setdefault(c, 0)
        n_dic[c] += b
    
    com_list = []

    for score, num in n_dic.items():
        heapq.heappush(com_list, (-score, num))
    
    taken = 0
    result = 0

    while True:
        score, num = heapq.heappop(com_list)
        score = -score
        if N - taken > num:
            result += score * num
            taken += num
        else:
            result += score * (N - taken)
            break
    
    print(result)

main()
Buggy python submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline

N, W = map(int, input().split())
items = [list(map(int, input().split())) for i in range(N)]

dpt = [0] * (W+1)

for w, v in items:
    for j in range(W, w-1, -1):
        a = dpt[j]
        b = dpt[j-w]+v
        if a > b:
            dpt[j] = a
        else:
            dpt[j] = b

print(dpt[W])


Fixed submission:
import math
N = int(input())
step_list = list(map(int, input().split()))

dp_table = [math.inf] * N
dp_table[0] = 0

for i in range(1, N):
    if i <= 1:
        dp_table[i] = dp_table[i-1] + abs(step_list[i-1] - step_list[i])
    else:
        dp_table[i] = min(dp_table[i-1] + abs(step_list[i-1] - step_list[i]),
                          dp_table[i-2] + abs(step_list[i-2] - step_list[i]))

print(dp_table[N-1])
Buggy python submission (verdict: Time Limit Exceeded):
import math
N, K = map(int, input().split())

dpt = [math.inf] * N
steps = list(map(int, input().split()))
dpt[0] = 0
for i in range(N):
    for j in range(1, K+1):
        if i + j > N - 1:
            break
        ij = i + j
        x = dpt[i] + abs(steps[i] - steps[ij])
        if x < dpt[ij]:
            dpt[ij] = x

print(dpt[N-1])


Fixed submission:
import math
step_n, max_jump = map(int, input().split())

step_list = list(map(int, input().split()))

dp_table = [math.inf] * (step_n)
dp_table[0] = 0

for i in range(1, step_n):
    min_from = max(0, i - max_jump)
    dp_table[i] = min(dp_table[j] + abs(step_list[i] - step_list[j]) for j in range(min_from, i))

print(dp_table[step_n-1])

Buggy python submission (verdict: Time Limit Exceeded):
import math
step_n, max_jump = map(int, input().split())

step_list = list(map(int, input().split()))

dp_table = [math.inf] * (step_n)
dp_table[0] = 0

def jump_cost(step_a, step_b):
    return abs(step_list[step_a] - step_list[step_b])

for i in range(1, step_n):
    min_from = max(0, i - max_jump)
    min_cost = math.inf
    for j in range(min_from, i):
        cost = dp_table[j] + jump_cost(i, j)
        if min_cost > cost:
            min_cost = cost
    dp_table[i] = min_cost

print(dp_table[step_n-1])



Fixed submission:
import math
step_n, max_jump = map(int, input().split())

step_list = list(map(int, input().split()))

dp_table = [math.inf] * (step_n)
dp_table[0] = 0

for i in range(1, step_n):
    min_from = max(0, i - max_jump)
    dp_table[i] = min(dp_table[j] + abs(step_list[i] - step_list[j]) for j in range(min_from, i))

print(dp_table[step_n-1])

Buggy python submission (verdict: Time Limit Exceeded):
import math
step_n, max_jump = map(int, input().split())

step_list = list(map(int, input().split()))

dp_table = [math.inf] * (step_n)
dp_table[0] = 0

def jump_cost(step_a, step_b):
    return abs(step_list[step_a] - step_list[step_b])

for i in range(1, step_n):
    min_from = max(0, i - max_jump)
    dp_table[i] = min(dp_table[j] + jump_cost(i, j) for j in range(min_from, i))

print(dp_table[step_n-1])



Fixed submission:
import math
step_n, max_jump = map(int, input().split())

step_list = list(map(int, input().split()))

dp_table = [math.inf] * (step_n)
dp_table[0] = 0

for i in range(1, step_n):
    min_from = max(0, i - max_jump)
    dp_table[i] = min(dp_table[j] + abs(step_list[i] - step_list[j]) for j in range(min_from, i))

print(dp_table[step_n-1])
Buggy python submission (verdict: Time Limit Exceeded):
import math
def main():
    dpt = [math.inf] * (10**3*N + 1)
    dpt[0] = 0
    for w, v in items:
        for i in range(len(dpt)-1, v-1, -1):
            dpt[i] = min(dpt[i], dpt[i-v]+w)

    for i in range(len(dpt)-1, -1, -1):
        if dpt[i] <= W:
            break
    print(i)





if __name__ == '__main__':
    N, W = map(int, input().split())
    items = [list(map(int, input().split())) for i in range(N)]
    main()

Fixed submission:
import numpy as np
import numba
import math

@numba.njit
def main():
    dpt = np.array([math.inf] * (10**3*N + 1))
    dpt[0] = 0
    for i in range(N):
        for j in range(len(dpt)-1, items[i][1]-1, -1):
            dpt[j] = min(dpt[j], dpt[j-items[i][1]]+items[i][0])

    for i in range(len(dpt)-1, -1, -1):
        if dpt[i] <= W:
            break
    print(i)

if __name__ == '__main__':
    N, W = map(int, input().split())
    items = np.array([list(map(int, input().split())) for i in range(N)])
    main()
Buggy python submission (verdict: Runtime Error):
import resource, sys
resource.setrlimit(resource.RLIMIT_STACK, (2**29,-1))
sys.setrecursionlimit(10**9)

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

paths = [[] for i in range(N)]
longest_paths = [-1 for i in range(N)]

for i in range(M):
    x, y = map(int, input().split())
    paths[x-1].append(y-1)

def get_longest(node):
    if longest_paths[node] != -1:
        return longest_paths[node]
    if paths[node] == []:
        longest_paths[node] = 0
        return 0
    else:
        result = max([get_longest(nd) for nd in paths[node]]) + 1
        longest_paths[node] = result
        return result

print(max([get_longest(i) for i in range(N)]))

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

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

paths = [[] for i in range(N)]
longest_paths = [-1 for i in range(N)]

for i in range(M):
    x, y = map(int, input().split())
    paths[x-1].append(y-1)

def get_longest(node):
    if longest_paths[node] != -1:
        return longest_paths[node]
    if paths[node] == []:
        longest_paths[node] = 0
        return 0
    else:
        result = max([get_longest(nd) for nd in paths[node]]) + 1
        longest_paths[node] = result
        return result

print(max([get_longest(i) for i in range(N)]))

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

paths = [[] for i in range(N)]
longest_paths = [-1 for i in range(N)]

for i in range(M):
    x, y = map(int, input().split())
    paths[x-1].append(y-1)

def get_longest(node):
    if longest_paths[node] != -1:
        return longest_paths[node]
    if paths[node] == []:
        longest_paths[node] = 0
        return 0
    else:
        result = max([get_longest(nd) for nd in paths[node]]) + 1
        longest_paths[node] = result
        return result

print(max([get_longest(i) for i in range(N)]))

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

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

paths = [[] for i in range(N)]
longest_paths = [-1 for i in range(N)]

for i in range(M):
    x, y = map(int, input().split())
    paths[x-1].append(y-1)

def get_longest(node):
    if longest_paths[node] != -1:
        return longest_paths[node]
    if paths[node] == []:
        longest_paths[node] = 0
        return 0
    else:
        result = max([get_longest(nd) for nd in paths[node]]) + 1
        longest_paths[node] = result
        return result

print(max([get_longest(i) for i in range(N)]))
Buggy python submission (verdict: Runtime Error):
H, W = map(int, input().split())
field = [input() for i in range(H)]
route_count_memory = [[-1] * W for i in range(H)]
route_count_memory[0][0] = 1

def get_route_count(i,j):
    result = 0
    if route_count_memory[i][j] != -1:
        return route_count_memory[i][j]
    if 0 <= i-1 < H and field[i-1][j] != '#':
        result += get_route_count(i-1, j)
    if 0 <= j-1 < W and field[i][j-1] != '#':
        result += get_route_count(i, j-1)
    route_count_memory[i][j] = result
    return result

print(get_route_count(H-1, W-1)%(10**9+7))


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

H, W = map(int, input().split())
field = [input() for i in range(H)]
route_count_memory = [[-1] * W for i in range(H)]
route_count_memory[0][0] = 1

def get_route_count(i,j):
    result = 0
    if route_count_memory[i][j] != -1:
        return route_count_memory[i][j]
    if 0 <= i-1 < H and field[i-1][j] != '#':
        result += get_route_count(i-1, j)
    if 0 <= j-1 < W and field[i][j-1] != '#':
        result += get_route_count(i, j-1)
    route_count_memory[i][j] = result
    return result

print(get_route_count(H-1, W-1)%(10**9+7))
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
head_prob_table = [[0] * (N+1) for i in range(N)]
head_prob = list(map(float, input().split()))

head_prob_table[0][1] = head_prob[0]
head_prob_table[0][0] = 1-head_prob[0]

for i in range(1, N):
    for j in range(i+2):
        prob = 0
        prob += head_prob_table[i-1][j] * (1 - head_prob[i])
        if j > 0:
            prob += head_prob_table[i-1][j-1] * head_prob[i]
        head_prob_table[i][j] = prob

print(sum(head_prob_table[N-1][(N+1)//2:]))


Fixed submission:
N = int(input())
def main():
    head_prob_table = [[0.0] * (N+1) for i in range(N)]
    head_prob = list(map(float, input().split()))

    head_prob_table[0][1] = head_prob[0]
    head_prob_table[0][0] = 1-head_prob[0]

    for i in range(1, N):
        for j in range(i+2):
            head_prob_table[i][j] += head_prob_table[i-1][j] * (1 - head_prob[i])
            if j > 0:
                head_prob_table[i][j] += head_prob_table[i-1][j-1] * head_prob[i]

    print(sum(head_prob_table[N-1][(N+1)//2:]))

if __name__ == '__main__':
    main()
Buggy python submission (verdict: Runtime Error):
import numpy as np
from numba import njit

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

max_candies = np.array(list(map(int, input().split())))

dpt = np.full((N+1, K+1), 0, dtype='int64')
for i in range(K+1):
    dpt[0][i] = 1

@njit('i8(i8,i8,i8[:],i8[:,:]', cache=True)
def dp(N, K, max_candies, dpt):
    for i in range(1, N+1):
        for j in range(0, K+1):
            dpt[i][j] += dpt[i-1][j]
            t = j - max_candies[i-1] - 1
            if t >= 0:
                dpt[i][j] -= dpt[i-1][t]
            if j > 0:
                dpt[i][j] += dpt[i][j-1]
            dpt[i][j] = dpt[i][j] % (10**9+7)
    return (dpt[N][K] - dpt[N][K-1]) % (10**9+7)

if K > 0:
    print(dp(N, K, max_candies, dpt))
else:
    print(1)


Fixed submission:
import numpy as np
from numba import njit

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

max_candies = np.array(list(map(int, input().split())))

dpt = np.full((N+1, K+1), 0, dtype='int64')
for i in range(K+1):
    dpt[0][i] = 1

@njit
def dp(N, K, max_candies, dpt):
    for i in range(1, N+1):
        for j in range(0, K+1):
            dpt[i][j] += dpt[i-1][j]
            t = j - max_candies[i-1] - 1
            if t >= 0:
                dpt[i][j] -= dpt[i-1][t]
            if j > 0:
                dpt[i][j] += dpt[i][j-1]
            dpt[i][j] = dpt[i][j] % (10**9+7)
    return (dpt[N][K] - dpt[N][K-1]) % (10**9+7)

if K > 0:
    print(dp(N, K, max_candies, dpt))
else:
    print(1)