Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

h, w, k= map(int, input().split())


if k%h==0 or k%w==0:
    print('Yes')
    exit()

if w!=2:
    for i in range(1,w):
        if (k-i*h) % (w-i*2) == 0 and 0<(k-i*h) // (w-i*2)<=h:
            print('Yes')
            exit()

if h!=2:
    for i in range(1,h):
        if (k-i*w) % (h-i*2) == 0 and 0<(k-i*w) // (h-i*2)<=h:
            print('Yes')
            exit()

print('No')


Fixed submission:
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

h, w, k= map(int, input().split())

if k%h==0 or k%w==0:
    print('Yes')
    exit()

for i in range(1,w):
    if w-i*2 != 0:
        if (k-i*h) % (w-i*2) == 0 and 0<(k-i*h) // (w-i*2)<=h:
            print('Yes')
            exit()

for i in range(1,h):
    if h-i*2 != 0:
        if (k-i*w) % (h-i*2) == 0 and 0<(k-i*w) // (h-i*2)<=w:
            print('Yes')
            exit()

print('No')
Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

n = int(input())

d = [[float('inf')]*n for i in range(n)]

for i in range(n):
    d[i] = list( map(int, input().split()))

for i in range(n):
    if d[i][i] != 0:
        print(-1)
        exit()

for k in range(n):
    for i in range(n):
        for j in range(n):
            if d[i][j] > d[i][k] + d[k][j]:
                print(-1)
                exit()

ans = 0
for i in range(n):
    for j in range(n):
        for k in range(n):
            if i==k or k==j :continue
            if d[i][j] == d[i][k] + d[k][j]:
                break
        else:
            ans += d[i][j]

print(ans//2)


Fixed submission:
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

n = int(input())

d = [[float('inf')]*n for i in range(n)]

for i in range(n):
    d[i] = list( map(int, input().split()))

for i in range(n):
    if d[i][i] != 0:
        print(-1)
        exit()

for k in range(n):
    for i in range(n):
        for j in range(n):
            if d[i][j] > d[i][k] + d[k][j]:
                print(-1)
                exit()

ans = 0
for i in range(n):
    for j in range(n):
        for k in range(n):
            if i==k or k==j :continue
            if d[i][j] == d[i][k] + d[k][j]:
                break
        else:
            ans += d[i][j]

print(ans//2)
Buggy python submission (verdict: Time Limit Exceeded):
# --- ワーシャルフロイド 任意のペアに対して最短距離を求める（非負）
def warshall_floyd(dp):
    for k in range(n):
        for i in range(n):
            for j in range(n):
                dp[i][j] = min(dp[i][j] , dp[i][k] + dp[k][j])
    return dp

n, m,R = map(int, input().split())
r = list( map(int, input().split()))

d = [[float("inf")]*n for i in range(n)]

abc = [tuple(map(int,input().split())) for i in range(m)]
for a,b,c in abc:
    a,b = a-1,b-1
    d[a][b] = c
    d[b][a] = c

for i in range(n):
    d[i][i] = 0

warshall_floyd(d)

import itertools

p = itertools.permutations(r, R)

INF = float('inf')
ans = INF
for path in p:
    tmp = 0
    for i in range(R-1):
        tmp += d[path[i]-1][path[i+1]-1]
    ans = min(ans,tmp)

print(ans)


Fixed submission:
# --- ワーシャルフロイド 任意のペアに対して最短距離を求める（非負）
def warshall_floyd(dp):
    for k in range(n):
        for i in range(n):
            for j in range(n):
                dp[i][j] = min(dp[i][j] , dp[i][k] + dp[k][j])
    return dp

n, m,R = map(int, input().split())
r = list( map(int, input().split()))

d = [[float("inf")]*n for i in range(n)]

abc = [tuple(map(int,input().split())) for i in range(m)]
for a,b,c in abc:
    a,b = a-1,b-1
    d[a][b] = c
    d[b][a] = c

for i in range(n):
    d[i][i] = 0

warshall_floyd(d)

import itertools

p = itertools.permutations(r, R)

INF = float('inf')
ans = INF
for path in p:
    tmp = 0
    for i in range(R-1):
        tmp += d[path[i]-1][path[i+1]-1]
    ans = min(ans,tmp)

print(ans)
Buggy python submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

n, m = map(int, input().split())

abc = [tuple(map(int,input().split())) for i in range(m)]
es = [[] for i in range(n)]
for i,(a,b,c) in enumerate(abc):
    a,b = a-1,b-1
    es[i]=[a,b,c]

INF = float('inf')

#True : 負の経路が存在する
def find_negative_loop(n,w,es):
    #負の経路の検出
    #n:頂点数, w:辺の数, es[i]: [辺の始点,辺の終点,辺のコスト]
    d = [-INF] * n
    d[0] = 0
    #この始点はどこでもよい
    for i in range(n):
        for j in range(w):
            e = es[j]
            if d[e[1]] < d[e[0]] + e[2]:
                d[e[1]] = d[e[0]] + e[2]
                if i == n-1:
                    return INF
    return d[n-1]

ans = find_negative_loop(n,m,es)

if ans == INF:
    print('inf')
    exit()

print(ans)

Fixed submission:
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

n, m = map(int, input().split())
abc = [tuple(map(int,input().split())) for i in range(m)]
es = []
for a,b,c in abc:
    a,b = a-1,b-1
    es.append((a,b,c))

INF = float('inf')

def find_negative_loop(n,es,s):
    #負の経路の検出
    #n:頂点数, es[i]: [辺の始点,辺の終点,辺のコスト], s:始点
    dist = [-INF] * n
    dist[s] = 0

    for i in range(n):
        for a,b,c in es:
            if dist[b] < dist[a]+c:
                dist[b] = dist[a]+c
                # if i == n-1: # n回目にも更新が行われている場合，ループが存在する
                if i == n-1 and b==n-1: # 終点に影響を及ぼすループが存在する
                        return INF
    return dist[n-1]

ans = find_negative_loop(n,es,0)

if ans == INF:
    print('inf')
    exit()

print(ans)
Buggy python submission (verdict: Runtime Error):
s = list(input()) #sys.stdin.readlineは最後が改行
k = int(input())

now = 0

while k>0 and now<len(s):
    tmp = ord('z')-ord(s[now])+1
    if tmp<=k:
        s[now] = 'a'
        k -= tmp
        now+=1
    else:
        now+=1

if k>0:
    s[-1] = chr(ord(s[-1])+k )

print(*s,sep='')


Fixed submission:
s = list(input()) #sys.stdin.readlineは最後が改行
k = int(input())

now = 0

while k>0 and now<len(s):
    if s[now]=='a':
        now+=1
        continue
    tmp = ord('z')-ord(s[now])+1
    if tmp<=k:
        s[now] = 'a'
        k -= tmp
        now+=1
    else:
        now+=1

if k>0:
    s[-1] = chr(ord(s[-1])+k%26 )

print(*s,sep='')
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
a = list(map(int, input().split()))
mod = 10**9 + 7
a = [x%mod for x in a]
ans = 0
for i in range(n):
    for j in range(i+1, n):
        ans += (a[i] * a[j])
print(ans % mod)

Fixed submission:
n = int(input())
a = list(map(int, input().split()))
mod = 10**9 + 7
aa = [a[0] % mod]
for i in range(1, n-1):
    aa.append((aa[i-1] + a[i]) % mod)
ans = 0
for i in range(n-1):
    ans += ((aa[i] * a[i+1]) % mod)
print(ans % mod)
Buggy python submission (verdict: Time Limit Exceeded):
s = input()
table = [0 for i in range(2019)]
table[0] = 1
num = 0
d = 1
for c in s[::-1]:
    num += (int(c) * d)
    num %= 2019
    d *= 10
    table[num] += 1

ans = 0
for cnt in table:
    ans += cnt * (cnt - 1) // 2

print(ans)

Fixed submission:
s = input()
table = [0 for i in range(2019)]
table[0] = 1
num = 0
d = 1
for c in s[::-1]:
    num += (int(c) * d)
    num %= 2019
    d *= 10
    d %= 2019
    table[num] += 1

ans = 0
for cnt in table:
    ans += cnt * (cnt - 1) // 2

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
s = input()
table = [0 for i in range(2019)]
table[0] = 1
num = 0
d = 1
for c in s[::-1]:
    num += (int(c) * d)
    num %= 2019
    d *= 10
    table[num] += 1

ans = 0
for cnt in table:
    ans += cnt * (cnt - 1) // 2

print(ans)

Fixed submission:
s = input()
table = [0 for i in range(2019)]
table[0] = 1
num = 0
d = 1
for c in s[::-1]:
    num += (int(c) * d)
    num %= 2019
    d *= 10
    d %= 2019
    table[num] += 1

ans = 0
for cnt in table:
    ans += cnt * (cnt - 1) // 2

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
s = input()
table = [0 for i in range(len(s)+1)]
i = 1
for c in s[::-1]:
    table[i] = ((10 ** (i-1)) * int(c) + table[i-1]) % 2019
    i += 1

ans =  len(s) + 1 - len(set(table))
print(ans)

Fixed submission:
s = input()
table = [0 for i in range(2019)]
table[0] = 1
num = 0
d = 1
for c in s[::-1]:
    num += (int(c) * d)
    num %= 2019
    d *= 10
    d %= 2019
    table[num] += 1

ans = 0
for cnt in table:
    ans += cnt * (cnt - 1) // 2

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

n = int(input())
a = list(map(int, input().split(' ')))
c = collections.Counter(a)
dict_1 = {}
dict_2 = {}
for key, value in c.items():
    dict_1[key] = value * (value-1) // 2
    if value - 1 == 0:
        dict_2[key] = 0
    else:
        dict_2[key] = (value-1) * (value-2) // 2
    
for k in range(n):
    ans = 0
    for key, val in dict_1.items():
        if key == a[k]:
            ans += dict_2[key]
        else:
            ans += dict_1[key]
    print(ans)

Fixed submission:
n = int(input())
a = list(map(int, input().split(' ')))
dic = {}
com = {}
ans = 0
for v in a:
    try:
        t = dic[v]
        ans += t
        com[v] += t
        dic[v] += 1
    except:
        dic[v] = 1
        com[v] = 0

for k in range(n):
    print(ans - (dic[a[k]]-1))

Buggy python submission (verdict: Time Limit Exceeded):
import collections

n = int(input())
a = list(map(int, input().split(' ')))
c = collections.Counter(a)
dict_1 = {}
dict_2 = {}
for key, value in c.items():
    dict_1[key] = value * (value-1) // 2
    if value - 1 == 0:
        dict_2[key] = 0
    else:
        dict_2[key] = (value-1) * (value-2) // 2
    
for k in range(n):
    ans = 0
    for key, val in dict_1.items():
        if key == a[k]:
            ans += dict_2[key]
        else:
            ans += dict_1[key]
    print(ans)

Fixed submission:
n = int(input())
a = list(map(int, input().split(' ')))
dic = {}
com = {}
ans = 0
for v in a:
    try:
        t = dic[v]
        ans += t
        com[v] += t
        dic[v] += 1
    except:
        dic[v] = 1
        com[v] = 0

for k in range(n):
    print(ans - (dic[a[k]]-1))
Buggy python submission (verdict: Time Limit Exceeded):
s = input()
n = int(input())
a = []
b = []
reverse_flag = False

for i in range(n):
    command = input()
    # reverse
    if len(command) == 1:
        reverse_flag = not reverse_flag
    
    else:
        _, t, f = command.split(' ')
        if t == '1':
            if reverse_flag:
                b.append(f)
            else:
                a.insert(0, f)
        else:
            if reverse_flag:
                
                a.insert(0, f)
            else:
                b.append(f)

if reverse_flag:
    print(''.join(b[::-1]) + s[::-1] + ''.join(a[::-1]))
else:
    print(''.join(a) + s + ''.join(b))

Fixed submission:
from collections import deque

s = input()
n = int(input())
a = deque()
b = deque()
reverse_flag = False

for i in range(n):
    command = input()
    # reverse
    if len(command) == 1:
        reverse_flag = not reverse_flag
    
    else:
        _, t, f = command.split(' ')
        if t == '1':
            if reverse_flag:
                b.append(f)
            else:
                a.appendleft(f)
        else:
            if reverse_flag:
                
                a.appendleft(f)
            else:
                b.append(f)

a = list(a)
b = list(b)
if reverse_flag:
    print(''.join(b[::-1]) + s[::-1] + ''.join(a[::-1]))
else:
    print(''.join(a) + s + ''.join(b))

Buggy python submission (verdict: Time Limit Exceeded):
s = input()
n = int(input())
a = []
b = []
reverse_flag = False

for i in range(n):
    command = input()
    # reverse
    if len(command) == 1:
        reverse_flag = not reverse_flag
    
    else:
        _, t, f = command.split(' ')
        if t == '1':
            if reverse_flag:
                b.append(f)
            else:
                a.insert(0, f)
        else:
            if reverse_flag:
                
                a.insert(0, f)
            else:
                b.append(f)

if reverse_flag:
    print(''.join(b[::-1]) + s[::-1] + ''.join(a[::-1]))
else:
    print(''.join(a) + s + ''.join(b))

Fixed submission:
from collections import deque

s = input()
n = int(input())
a = deque()
b = deque()
reverse_flag = False

for i in range(n):
    command = input()
    # reverse
    if len(command) == 1:
        reverse_flag = not reverse_flag
    
    else:
        _, t, f = command.split(' ')
        if t == '1':
            if reverse_flag:
                b.append(f)
            else:
                a.appendleft(f)
        else:
            if reverse_flag:
                
                a.appendleft(f)
            else:
                b.append(f)

a = list(a)
b = list(b)
if reverse_flag:
    print(''.join(b[::-1]) + s[::-1] + ''.join(a[::-1]))
else:
    print(''.join(a) + s + ''.join(b))
Buggy python submission (verdict: Runtime Error):
import numpy as np

a = [[0] * 3 for i in range(3)]
for i in range(3):
    a[i] = list(map(int, input().split(' ')))

n = int(input())

for i in range(n):
    b = int(input())
    
    for r in range(3):
        for c in range(3):
            if a[r][c] == b:
                a[r][c] = 0

a = np.array(a)
sum1 = a.sum(axis=0)
sum2 = a.sum(axis=1)
naname1 = a[0][0] + a[1][1] + a[2][2]
naname2 = a[0][2] + a[1][1] + a[2][0]

if 0 in sum1 or 0 in sum2 or naname1 == 0 or naname2 == 0:
    print('Yes')
else:
    print('No')

Fixed submission:
import numpy as np

a = [[0] * 3 for i in range(3)]
for i in range(3):
    a[i] = list(map(int, input().split(' ')))

n = int(input())

for i in range(n):
    b = int(input())
    
    for r in range(3):
        for c in range(3):
            if a[r][c] == b:
                a[r][c] = 0

a = np.array(a)
sum1 = a.sum(axis=0)
sum2 = a.sum(axis=1)
naname1 = a[0][0] + a[1][1] + a[2][2]
naname2 = a[0][2] + a[1][1] + a[2][0]

if 0 in sum1 or 0 in sum2 or naname1 == 0 or naname2 == 0:
    print('Yes')
else:
    print('No')

Buggy python submission (verdict: Runtime Error):
a = [[0] * 3 for i in range(3)]
for i in range(3):
    a[i] = list(map(int, input().split(' ')))

n = int(input())

for i in range(n):
    b = int(input())
    
    for r in range(3):
        for c in range(3):
            if a[r][c] == b:
                a[r][c] = 0

a = np.array(a)
sum1 = a.sum(axis=0)
sum2 = a.sum(axis=1)
naname1 = a[0][0] + a[1][1] + a[2][2]
naname2 = a[0][2] + a[1][1] + a[2][0]

if 0 in sum1 or 0 in sum2 or naname1 == 0 or naname2 == 0:
    print('Yes')
else:
    print('No')

Fixed submission:
import numpy as np

a = [[0] * 3 for i in range(3)]
for i in range(3):
    a[i] = list(map(int, input().split(' ')))

n = int(input())

for i in range(n):
    b = int(input())
    
    for r in range(3):
        for c in range(3):
            if a[r][c] == b:
                a[r][c] = 0

a = np.array(a)
sum1 = a.sum(axis=0)
sum2 = a.sum(axis=1)
naname1 = a[0][0] + a[1][1] + a[2][2]
naname2 = a[0][2] + a[1][1] + a[2][0]

if 0 in sum1 or 0 in sum2 or naname1 == 0 or naname2 == 0:
    print('Yes')
else:
    print('No')
Buggy python submission (verdict: Runtime Error):
import fractions
import math


n, m = map(int, input().split())
a = list(map(int, input().split()))
flag = [divide_two(i) for i in a]

if sum(flag) != flag[0] * n:
    ans = 0
else:
    # 最小公倍数求める
    lcm = a[0]
    for i in range(1, n):
        lcm = lcm * a[i] // fractions.gcd(lcm, a[i])

    ans = math.floor(m / lcm + 0.5)
print(ans)

Fixed submission:
import fractions
import math

def divide_two(x):
    ans = 0
    while x > 0:
        if x % 2 == 0:
            ans += 1
            x = x // 2
        else:
            break
    return ans

n, m = map(int, input().split())
a = list(map(int, input().split()))
flag = [divide_two(i) for i in a]

if sum(flag) != flag[0] * n:
    ans = 0
else:
    # 最小公倍数求める
    lcm = a[0]
    for i in range(1, n):
        lcm = lcm * a[i] // fractions.gcd(lcm, a[i])

    ans = math.floor(m / lcm + 0.5)
print(ans)
Buggy python submission (verdict: Runtime Error):
import math

a, b = map(int, input().split())
gcd = math.gcd(a, b)
ans = int(a*b/gcd)
print(ans)

Fixed submission:
def get_gcd(a, b):
    if a < b:
        a, b = b, a
    r = -1
    while r:
        r = a % b
        a = b
        b = r
    return a

a, b = map(int, input().split())
g = get_gcd(a, b)
ans = int(a * b / g)
print(ans)
Buggy python submission (verdict: Runtime Error):
n, k, q = map(int, input().split())

scores = [0 for i in range(n)]

for a in range(q):
    scores[a-1] += 1

for s in scores:
    if q - s >= k:
        print('No')
    else:
        print('Yes')

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

scores = [0 for i in range(n)]

for i in range(q):
    a = int(input())
    scores[a-1] += 1

for s in scores:
    if q - s >= k:
        print('No')
    else:
        print('Yes')
Buggy python submission (verdict: Runtime Error):
n = int(input())
h = list(map(int, input().split()))

ans = 0
start_flg = True
for i in range(n-1):
    if start_flg:
        temp = 0

    if h[i] >= h[i+1]:
        temp += 1
        start_flg = False
    else:
        ans = max(ans, temp)
        start_flg = True
ans = max(ans, temp)

print(ans)


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

ans = 0
temp = 0
start_flg = True
for i in range(n-1):
    if start_flg:
        temp = 0

    if h[i] >= h[i+1]:
        temp += 1
        start_flg = False
    else:
        ans = max(ans, temp)
        start_flg = True
ans = max(ans, temp)

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = lambda: sys.stdin.readline().rstrip("\r\n")

mod = 998244353

n, k = map(int, input().split())
s = set()
for _ in range(k):
    l, r = map(int, input().split())
    for i in range(l, r + 1):
        s.add(i)

dp = [0] * (n + 1)
dp[0] = 1

for i in range(1, n + 1):
    for j in range(i):
        if i - j in s:
            dp[i] += dp[j]
            dp[i] %= mod

print(dp[-2])
    

Fixed submission:
import sys
input = lambda: sys.stdin.readline().rstrip("\r\n")

mod = 998244353

n, k = map(int, input().split())
l = []
r = []
for _ in range(k):
    l_, r_ = map(int, input().split())
    l.append(l_)
    r.append(r_)
dp = [0] * (n + 1)
dp_csum = [0] * (n + 1)
dp[1] = 1
dp_csum[1] = 1
for i in range(2, n + 1):
    for j in range(k):
        left = i - r[j]
        right = i - l[j]
        if right >= 1:
            dp[i] += dp_csum[right] - dp_csum[max(left, 1) - 1]
            dp[i] %= mod
    dp_csum[i] = dp_csum[i - 1] + dp[i]
    dp_csum[i] %= mod
print(dp[-1])
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = lambda: sys.stdin.readline().rstrip("\r\n")

h, w = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())
ch -= 1
cw -= 1
dh -= 1
dw -= 1
s = []
for _ in range(h):
    s.append(list(input()))
from collections import deque
def bfs(x, y):
    ans = 0
    d = [[float('inf')]*w for _ in range(h)]
    d[x][y] = 0
    queue = deque([(x, y)])

    while queue:
        x, y = queue.popleft()
        for i in range(-2, 3):
            for j in range(-2, 3):
                u = x + i
                v = y + j

                if 0 <= u < h and 0 <= v < w and s[u][v] == '.' and d[u][v] > d[x][y]:
                    if abs(i) + abs(j) <= 1:
                        d[u][v] = min(d[x][y], d[u][v])
                    else:
                        d[u][v] = min(d[u][v], d[x][y] + 1)
                    queue.append((u, v))
    return d

d = bfs(ch, cw)
if d[dh][dw] == float('inf'):
    print(-1)
else:
    print(d[dh][dw])

    


Fixed submission:
import sys
input = lambda: sys.stdin.readline().rstrip("\r\n")

import sys
input = lambda: sys.stdin.readline().rstrip("\r\n")

h, w = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())
ch -= 1
cw -= 1
dh -= 1
dw -= 1
s = []
for _ in range(h):
    s.append(list(input()))
from collections import deque, defaultdict
def bfs(x, y):
    wp = defaultdict(list)
    d = [[-1] * w for _ in range(h)]
    d[x][y] = 0
    queue = deque([(x, y)])
    while queue:
        u, v = queue.popleft()
        wp[0].append((u, v))
        next_grid = [(u - 1, v), (u + 1, v), (u, v - 1), (u, v + 1)]
        for x, y in next_grid:
            if 0 <= x < h and 0 <= y < w and s[x][y] != '#' and d[x][y] < 0:
                d[x][y] = d[u][v]
                queue.append((x, y))
    for i in range(10**6):
        if len(wp[i]) == 0:
            break
        queue = deque([])
        for x, y in wp[i]:
            for dx in range(-2, 3):
                for dy in range(-2, 3):
                    u, v = x + dx, y + dy
                    if 0 <= u < h and 0 <= v < w and s[u][v] == '.' and d[u][v] < 0:
                        d[u][v] = i + 1
                        queue.append((u, v))
        while queue:
            u, v = queue.popleft()
            wp[i + 1].append((u, v))
            next_grid = [(u - 1, v), (u + 1, v), (u, v - 1), (u, v + 1)]
            for x, y in next_grid:
                if 0 <= x < h and 0 <= y < w and s[x][y] != '#' and d[x][y] < 0:
                    d[x][y] = d[u][v]
                    queue.append((x, y))
    return d

d = bfs(ch, cw)
print(d[dh][dw])
Buggy python submission (verdict: Runtime Error):
import sys
input = lambda: sys.stdin.readline().rstrip("\r\n")

n, k = map(int, input().split())
a = [int(x) for x in input().split()]

left = -1
right = 10**9 + 1

while right - left > 1:
    mid = (right + left) // 2
    cnt = 0
    for b in a:
        cnt += b // mid + int(b % mid != 0) - 1
    if cnt <= k:
        right = mid
    else:
        left = mid
print(right)

Fixed submission:
import sys
input = lambda: sys.stdin.readline().rstrip("\r\n")

n, k = map(int, input().split())
a = [int(x) for x in input().split()]

left = 0
right = 10**9 + 1

while right - left > 1:
    mid = (right + left) // 2
    cnt = 0
    for b in a:
        cnt += b // mid + int(b % mid != 0) - 1
    if cnt <= k:
        right = mid
    else:
        left = mid
print(right)
Buggy python submission (verdict: Runtime Error):
import sys
input = lambda: sys.stdin.readline().rstrip("\r\n")

n = int(input())
a = [int(x) for x in input().split()]

sold_day = set()
buy_day = set()

for i in range(1, n):
    if a[i] > a[i - 1]:
        sold_day.add(i)
        buy_day.discard(i - 1)

money = 1000
stock = 0

sold_day = list(sold_day)
sold_day.sort()

s = 0

for i in sold_day:
    temp = a[s:i]
    min_value = min(temp)
    x = money // min_value
    money -= min_value * x
    money += x * a[i]
    s = i + 1
print(money)


Fixed submission:
import sys
input = lambda: sys.stdin.readline().rstrip("\r\n")

n = int(input())
a = [int(x) for x in input().split()]

sold_day = set()
buy_day = set()

for i in range(1, n):
    if a[i] > a[i - 1]:
        sold_day.add(i)
        sold_day.discard(i - 1)

money = 1000
stock = 0

sold_day = list(sold_day)
sold_day.sort()

s = 0

for i in sold_day:
    temp = a[s:i]
    min_value = min(temp)
    x = money // min_value
    money -= min_value * x
    money += x * a[i]
    s = i + 1
print(money)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = lambda: sys.stdin.readline().rstrip("\r\n")
import random
import time
start_time = time.time()
D = int(input())
c = [int(x) for x in input().split()]
s = []
for _ in range(D):
    s.append([int(x) for x in input().split()])
t = [random.randint(1, 26) for x in range(D)]

def solve(t):
    last = [0]*26
    ans = 0
    for i in range(1, D + 1):
        ans += s[i - 1][t[i - 1] - 1]
        last[t[i - 1] - 1] = i
        for j in range(26):
            ans -= c[j]*(i - last[j])
    return ans
ans = solve(t)
while True:
    now_time = time.time()
    if now_time - start_time > 2:
        print(*t, sep='\n')
        break
    d, q = [random.randint(1, D), random.randint(1, 26)]
    temp = t[d - 1]
    t[d - 1] = q
    ans_2 = solve(t)
    if ans_2 > ans:
        ans = ans_2
    else:
        t[d - 1] = temp



Fixed submission:
import sys
input = lambda: sys.stdin.readline().rstrip("\r\n")
import random
D = int(input())
c = [int(x) for x in input().split()]
s = []
for _ in range(D):
    s.append([int(x) for x in input().split()])
t = [random.randint(1, 26) for x in range(D)]
last = [0]*26
ans = 0
for i in range(1, D + 1):
    ans += s[i - 1][t[i - 1] - 1]
    last[t[i - 1] - 1] = i
    for j in range(26):
        ans -= c[j]*(i - last[j])
    #print(ans)
print(*t, sep="\n")