Problem:


Score : 500 points

Problem Statement

We have N logs of lengths A_1,A_2,\cdots A_N.

We can cut these logs at most K times in total. When a log of length L is cut at a point whose distance from an end of the log is t (0<t<L), it becomes two logs of lengths t and L-t.

Find the shortest possible length of the longest log after at most K cuts, and print it after rounding up to an integer.

Constraints

1 \leq N \leq 2 \times 10^5

0 \leq K \leq 10^9

1 \leq A_i \leq 10^9

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N K
A_1 A_2 \cdots A_N

Output

Print an integer representing the answer.

Sample Input 1

2 3
7 9

Sample Output 1

4

First, we will cut the log of length 7 at a point whose distance from an end of the log is 3.5, resulting in two logs of length 3.5 each.

Next, we will cut the log of length 9 at a point whose distance from an end of the log is 3, resulting in two logs of length 3 and 6.

Lastly, we will cut the log of length 6 at a point whose distance from an end of the log is 3.3, resulting in two logs of length 3.3 and 2.7.

In this case, the longest length of a log will be 3.5, which is the shortest possible result. After rounding up to an integer, the output should be 4.

Sample Input 2

3 0
3 4 5

Sample Output 2

5

Sample Input 3

10 10
158260522 877914575 602436426 24979445 861648772 623690081 433933447 476190629 262703497 211047202

Sample Output 3

292638192



Sample input:
2 3
7 9


Sample output:
4

Submission status: Accepted

Solution code:
#import numpy as np
#import collections
#import math

#f = open('./input_E.txt')
#
#N,K = map(int, f.readline().split())
#A = list(map(int, f.readline().split()))

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

A.sort(reverse=True)

def nibu(small,big,KK,AA):
    mid = (small+big)//2
    k_list = [(x-1)//mid for x in AA]
    sum_k = sum(k_list)
    if sum_k <= KK: #達成可能 -> 答えはもっと小さい
        return small,mid # 不可能,可能
    else:
        return mid,big # 不可能,可能


if K==0:
    ans = A[0]
else:    
    lmin = 0
    lmax = A[0]
    
    while lmax - lmin >= 2:
        lmin, lmax = nibu(lmin,lmax,K,A)
    
    ans = lmax
    
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
n, k = map(int, input().split())
a = list(map(int, input().split()))

def f(x):
    cnt = 0
    for i in a:
        cnt += (i-1) // x
        if cnt > k:
            return False
    return True
            
ok = 10**9
ng = 0
while ok - ng > 1:
    mid = (ok + ng) // 2
    if f(mid):
        ok = mid
    else:
        ng = mid
print(ok)

Submission status: Accepted

Solution code:
import math

def f(n):
    x = 0
    for ai in a:
        x += math.ceil(ai/n)-1
    return x <= k

def solve(ng,ok):
    while abs(ok-ng) > 1:
        mid = (ok+ng)//2
        flag = f(mid)
        if flag:
            ok = mid
        else:
            ng = mid
    return ok

n,k = map(int,input().split())
a = list(map(int,input().split()))
print(solve(0,max(a)))

Submission status: Accepted

Solution code:
import math
def is_ok(K, N, A, length):
    s = 0
    for i in range(N):
        if A[i] > length:
            s += math.ceil(A[i] / length)-1
    return K >= s


N, K = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]
if K == 0:
    print(max(A))
    exit()
ok = max(A)
ng = 0
while abs(ok - ng) > 1:
    mid = (ok + ng) // 2
    if is_ok(K, N, A, mid):
        ok = mid
    else:
        ng = mid

print(math.ceil(ok))

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
a = list(map(int,input().split()))
s = sum(a)
x = [0]*n
t = 0
for i in range(n):
    y = int(a[i]/s * k)
    x[i] = [i, a[i], y, a[i]/(y+1)]
    t += y
x.sort(key= lambda val : val[3],reverse=True)
for i in range(k-t):
    x[i][2] += 1
ans = 0
for i in range(n):
    ans = max(ans, x[i][1]/(x[i][2]+1))
print(int(-(-ans//1)))

Submission status: Accepted

Solution code:
# 入力
n, k = map(int, input().split())
A = list(map(int, input().split()))

# 最大値をx以下にできるか
def check(x):
    cnt = 0
    for a in A:
        cnt += (a - 1) // x
    return cnt <= k

# めぐる式二分探索
ok = 10 ** 10
ng = 0
while ok - ng > 1:
    mid = (ok + ng) // 2
    if check(mid):
        ok = mid
    else:
        ng = mid

# 出力
print(ok)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import sys
input=sys.stdin.readline

n,k=map(int,input().split())
arr=list(map(int,input().split()))
l=0
r=max(arr)+1
while r-l!=1:
    persuit=(r+l)//2
    cnt=0
    for val in arr:
        if val<=persuit:
            continue
        if val%persuit==0:
            cnt+=val//persuit-1
        else:
            cnt+=val//persuit
    if cnt<=k:
        r=persuit
    else:
        l=persuit
print(r)

Submission status: Accepted

Solution code:
import math
n,k = map(int,input().split())
alist = list(map(int,input().split()))

max_length = max(alist)
cur_length = 0

while(max_length - cur_length > 1):
    next_length = (max_length+cur_length)//2

    test_k = 0
    for i in range(n):
        test_k += math.ceil(alist[i]/next_length)-1

    if test_k <= k:
        max_length = next_length
    else:
        cur_length = next_length
        

print(max_length)

Submission status: Accepted

Solution code:
def resolve():
    import math
    n,k = map(int, input().split())
    a = list(map(int, input().split()))
    r = max(a)
    l = 0
    def cuttimes(p, cutter):
        return math.ceil(p/cutter)-1

    while r-l > 1:
        mid = (r+l)//2
        cut = 0
        for i in range(n):
            cut += cuttimes(a[i], mid)

        if cut <= k:
            r = mid
        else:
            l = mid
    print(r)

resolve()

Submission status: Accepted

Solution code:
from math import ceil
N, K = list(map(int, input().split()))

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

def possible(A, K, target):
    count = 0

    for a in A:
        count += ceil(a / target) - 1
    return count <= K

left = 1
right = max(A)

while left < right:
    mid = (left + right) // 2
    if possible(A, K, mid):
        right = mid
    else:
        left = mid + 1

print(right)

Submission status: Accepted

Solution code:
import math

n, k = map(int, input().split())
a = list(map(int, input().split()))

floor = 0
ceil = max(a)


def cut(long, logs):
    cnt = 0
    for i in logs:
        cnt += math.ceil(i / long) - 1
    return cnt


while ceil - floor > 1:
    L = (ceil + floor)//2
    num = cut(L, a)
    if num <= k:
        ceil = L
    else:
        floor = L

print(ceil)

Submission status: Accepted

Solution code:
import sys
from math import ceil, floor

def cut_logs(x, a):
    return sum(ceil(ai / x) - 1 for ai in a)


def resolve(in_):
    n, k = map(int, next(in_).split())
    logs = tuple(map(int, next(in_).split()))  # A
    assert n == len(logs)
    max_logs = max(logs)

    lb = 0
    ub = max_logs
    while ub - lb > 1:
        mid = (ub + lb) // 2
        v = cut_logs(mid, logs)
        # print(f'{lb=} {mid=} {ub=} {v<=k=} {v=} {k=}')
        if v <= k:
            ub = mid
        else:
            lb = mid
    # print(f'end: {lb=} {mid=} {ub=} {v<=k=} {v=} {k=}')

    return ub


def main():
    answer = resolve(sys.stdin.buffer)
    print(answer)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
aes = list(map(int, input().split()))

bottom, top = 0, max(aes)

def ok(l):
  cnt = 0
  for a in aes:
    if a % l == 0:
      cnt += a // l - 1
    else:
      cnt += a // l
  return cnt <= k

while top - bottom > 1:
  mid = (bottom + top) // 2
  if ok(mid):
    top = mid
  else:
    bottom = mid

print(top)

Submission status: Accepted

Solution code:
def main():
    import sys
    def input(): return sys.stdin.readline().rstrip()
    n , k = map(int, input().split())
    a = list(map(int, input().split()))
    
    def check(m):
        cnt = 0
        for x in a:
            cnt += (x-1)//m
        return cnt <= k
        
    l, r = 0, max(a)
    while r-l > 1:
        m = (r+l)//2
        if check(m): r = m
        else: l = m
    print(r)

    


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N,K = map(int, input().split())
A = list(map(int, input().split()))
    
l,r = 0, max(A)
while r-l>1:
  mid = (l+r)//2
  cnt = 0
  for i in range(N):
    if A[i]%mid!=0:
      cnt+= A[i]//mid
    else:
      cnt += A[i]//mid - 1
            
  if cnt <= K:
    r = mid
  else:
    l = mid
print(r)

Submission status: Accepted

Solution code:
n, k=map(int, input().split())
a=list(map(int, input().split()))

right=max(a)
left=0
def logs(a, n, x):
    sm=0
    for i in range(n):
        sm+=(a[i]-1)//x
    if sm<=k:
        return True
    else:
        return False

def binary_search(left, right):
    while right - left > 1:
        center=(left+right)//2
        if logs(a, n, center):
            right=center
        else:
            left=center
    
    return right
        
print(binary_search(left, right))

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# coding: utf-8

# In[16]:


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


# In[49]:


low = 0
high = max(A)
def ok(x):
    cnt = 0
    for a in A:
        cnt += (a//x)
        if a%x == 0:
            cnt -= 1
    return cnt <= K
 
while high-low > 1:
    mid = (high+low)//2
    if ok(mid):
        high = mid
    else:
        low = mid
print(high)


# In[ ]:

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

def judge(x):
    cnt = 0
    
    for Ai in A:
        cnt += (Ai+x-1)//x-1
    
    return cnt<=K

def binary_search():
    l, r = 1, 10**9+100
    
    while l<=r:
        m = (l+r)//2
        
        if judge(m):
            r = m-1
        else:
            l = m+1
    
    return l

N, K = map(int, input().split())
A = list(map(int, input().split()))
print(binary_search())

Submission status: Accepted

Solution code:

def resolve():
    def is_ok(mid):
        cnt = 0
        for a in A:
            cnt += (a-1)//mid
        return cnt <= K

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

    ok = max(A)
    ng = 0
    while ok - ng > 1:
        mid = (ok+ng)//2
        if is_ok(mid):
            ok = mid
        else:
            ng = mid
    print(ok)


if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))

# bottom...最小0ずつ切る(不可能な方)、top...最大max(a)ずつ切る（可能な方）
bottom, top = 0, max(a)


while top - bottom > 1:
    mid = (top+bottom) // 2
    cnt = 0
    for i in a:
        cnt += i//mid
        if i%mid == 0:
            cnt -= 1
    if cnt <= k:
        top = mid
    else:
        bottom = mid

print(top)

Submission status: Accepted

Solution code:
n, k, *aa = map(int, open(0).read().split())

imp = 0
psbl = 10**9

while psbl - imp > 1:
    mid = (psbl + imp) // 2
    cost = sum(0--a//mid - 1 for a in aa)
    if cost <= k:
        psbl = mid
    else:
        imp = mid

print(psbl)

Submission status: Accepted

Solution code:
n,k=list(map(int,input().split()))
m=list(map(int,input().split()))
import math
def pos(h):
    p=0
    for i in range(n):
        p+=math.ceil(m[i]/h)-1
    return bool(p<=k)
l,r=1,max(m)
while l<r:
    mid=(l+r)//2
    if pos(mid):
        r=mid
    else:
        l=mid+1
print(l)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))

l = 0
r = 10**9+1

def ok(x):
    cnt = 0
    for b in a:
        cnt += (b//x)
        if b%x == 0:
            cnt -= 1
    return cnt <= k

while r-l > 1:
    md = (l+r)//2
    if ok(md):
        r = md
    else:
        l = md
print(r)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))


def ok(min_l):  # k回以内のカットで全てmin_l以下に出来るか？
    cnt = 0
    for L in a:

        # min_lが何本作れる？
        cnt += L // min_l
        # 割り切れない時、余った1本もcntに足す
        if L % min_l != 0:
            cnt += 1

        # 切る回数は、本数-1回
        cnt -= 1
    return cnt <= k

# 最初、leftはFalse, rightはTrue
# FFF...FFFTTT...TTT
# Tの左端の長さが欲しい

left = 0
right = max(a)

while right - left > 1:
    mid = (left + right) // 2
    if ok(mid):
        right = mid
    else:
        left = mid

print(right)

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
A=[int(i) for i in input().split()]
#AiをKi回切ると仮定した場合Ai/(Ki+1)
#Kiの総和はK
#つまりKiを動かしたときのmax_i Ai/(Ki+1)を最小化する
#2分探索！
#最小値をmidにするための回数はK回以内でOKか？
#計算量はNlog(maxA)なので通りそう
low=0
high=max(A)+1
#low できない
#high できる
while(high-low>1):
    mid=(high+low)//2
    #ceil(Ai/(Ki+1))=mid
    #ceil(x)-1<x<=ceil(x)
    #x<=ceil(x)<x+1
    #mid-1<Ai/(Ki+1)<=mid
    #Ai/(Ki+1)<=mid<Ai/(Ki+1)+1
    #Ai<=mid*(Ki+1)<Ai+Ki+1
    #Ai/mid<=Ki+1<Ai+Ki+1
    #floor(Ai/mid)<=Ai/mid<floor(Ai/mid)+1
    #Ai/midが整数ならKi=Ai/mid-1
    #Ai/midが整数でないならばKi=Ai/mid
    tmp=0
    for i in range(N):
        tmp+=A[i]//mid
        if A[i]%mid==0:
            tmp-=1
    if tmp<=K:
        high=mid
    else:
        low=mid
print(high)

Submission status: Accepted

Solution code:
# AFTER EDITORIAL


def solve(k, ls):
    n = len(ls)
    i0 = 1
    i1 = max(ls)
    i = (i0 + i1) // 2
    while i0 < i1:
        m = 0
        for a in ls:
            m += (a // i) - int(a % i == 0)
        if m <= k:
            i1 = i
            i = (i0 + i1) // 2
        else:
            i0 = i + 1
            i = (i0 + i1) // 2
    return i


def main(istr, ostr):
    n, k = list(map(int, istr.readline().strip().split()))
    ls = list(map(int, istr.readline().strip().split()))
    result = solve(k, ls)
    print(result, file=ostr)


if __name__ == "__main__":
    import sys

    main(sys.stdin, sys.stdout)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))

ok = 10 ** 9  # 解が存在する値
ng = 0  # 解が存在しない値


def solve(x):
    """
    一番長いのをx以下にできるか
    → 全部をx以下にするのに切る回数 <= K
    """
    res = 0
    for i in range(N):
        res += (A[i] - 1) // x

    return res <= K


while abs(ok - ng) > 1:
    mid = (ok + ng) // 2
    if solve(mid):
        ok = mid
    else:
        ng = mid

print(ok)

Submission status: Accepted

Solution code:
import math

def cut_num(length,max_length):
    return math.ceil(length/max_length)-1

n,k = map(int,input().split())
a = list(map(int,input().split()))

l = 1
r = 10**9

while l<r:
    mid = (l+r)//2
    count = 0
    for i in range(n):
        count += cut_num(a[i],mid)
    if count > k:
        l = mid+1
    else:
        r = mid
print(l)

Submission status: Accepted

Solution code:
#coding: utf-8
N, K = (int(n) for n in input().split())
A = [int(n) for n in input().split()]

def is_ok(X):
    return sum([-(-n // X) - 1 for n in A]) <= K

def meguru_bisect(ng, ok):
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if is_ok(mid):
            ok = mid
        else:
            ng = mid
    return ok

print(meguru_bisect(0, max(A)+1))

Submission status: Accepted

Solution code:
#coding: utf-8
N, K = (int(n) for n in input().split())
A = [int(n) for n in input().split()]

def is_ok(X):
    ret = 0
    for log in A:
        ret += -(-log//X) - 1
    return ret <= K

def meguru_bisect(ng, ok):
    '''
    初期値のng,okを受け取り,is_okを満たす最小(最大)のokを返す
    まずis_okを定義すべし
    ng ok は  とり得る最小の値-1 とり得る最大の値+1
    最大最小が逆の場合はよしなにひっくり返す
    '''
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if is_ok(mid):
            ok = mid
        else:
            ng = mid
    return ok

print(meguru_bisect(0, max(A)+1))

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))

def check(l):
    cnt = 0
    for _ in a:
        cnt += _ // l
        if _ % l != 0:
            cnt += 1
        cnt -= 1
    if cnt <= k: return True
    else : return False

"""
left: ng
right: ok
"""
def binary(ng, ok):
    while ok - ng > 1:
        mid = (ng + ok) // 2
        if check(mid): ok = mid
        else: ng = mid
    return ok

print(binary(0, max(a)))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n,k=map(int,input().split())
a=list(map(int,input().split()))
ok=10**10
ng=1
for i in range(40):
    chk=(ok+ng)//2
    cnt=0
    for j in range(n):
        cnt+=(a[j]+chk-1)//chk-1
    if cnt > k:
        ng = chk
    else:
        ok = chk
print(ok)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
ok=10**10
ng=1
for i in range(40):
    chk=(ok+ng)//2
    cnt=0
    for j in range(n):
        cnt+=(a[j]+chk-1)//chk-1
    if cnt > k:
        ng = chk
    else:
        ok = chk
print(ok)

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
 
N, K = map(int, readline().split())
A = list(map(int, readline().split()))
 
l = 0
r = 10**10
 
def test(m):
  return sum((a + m - 1) // m for a in A) - N <= K

while l + 1 < r:
  m = (l + r) // 2
  if test(m):
  	r = m
  else:
    l = m
print(r)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
A = list(map(int, input().split()))

max_a = max(A)
min_a = 0

while abs(max_a - min_a) > 1:
    cnt = 0
    target_length = (max_a + min_a)//2
    for a in A:
        cut_num = (a + target_length - 1)//target_length
        cnt += cut_num - 1
    if cnt > k:
        min_a = target_length
    else:
        if target_length - min_a == 1:
            print(target_length)
            exit()
        max_a = target_length

print(max_a)

Submission status: Accepted

Solution code:
import sys
import numpy as np
import math
def Ii():return int(sys.stdin.readline())
def Mi():return map(int,sys.stdin.readline().split())
def Li():return list(map(int,sys.stdin.readline().split()))
n,k = Mi()
a = np.array(sys.stdin.readline().split(), np.int64)
mina = np.sum(a//(n+k))
maxa = np.max(a)
while maxa > mina+1:
  mid = (mina+maxa)//2
  div = np.sum(np.ceil(a/mid-1))
  if div > k:
    mina = mid
  else:
    maxa = mid
  
print(maxa)

Submission status: Accepted

Solution code:
import sys
import numpy as np
import math
def Ii():return int(sys.stdin.readline())
def Mi():return map(int,sys.stdin.readline().split())
def Li():return list(map(int,sys.stdin.readline().split()))
n,k = Mi()
a = np.array(sys.stdin.readline().split(), np.int64)
sa = np.sum(a)
mina = sa//(n+k)
maxa = np.max(a)
while maxa > mina+1:
  mid = (mina+maxa)//2
  div = np.sum(np.ceil(a/mid-1))
  #print(mina,maxa,div)
  if div > k:
    mina = mid
  else:
    maxa = mid
  
print(maxa)

Submission status: Accepted

Solution code:
def check(numbers, threshold):
    
    total = 0
    
    for number in numbers:
        d, m = divmod(number, threshold)
        if m == 0:
            d -= 1
        total += d
    return total
    
def main():
    n, k = map(int, input().rstrip().split(" "))
    
    numbers = list(map(int, input().rstrip().split(" ")))
    
    bottom, top = 1, 2 * (10 ** 9)
    
    while bottom < top:
        #print(bottom, top)
        if check(numbers, (bottom + top )// 2) <= k:
            top = (bottom + top )// 2
        else:
            bottom = ((bottom + top )// 2) + 1
    print(top)
    
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#create date: 2020-08-03 14:18

import sys
stdin = sys.stdin

def ns(): return stdin.readline().rstrip()
def ni(): return int(ns())
def na(): return list(map(int, stdin.readline().split()))

def cut(a, l):
    res = 0
    for ai in a:
        res += max(0, (ai-1)//l)
        #print(ai, max(0, (ai-1)//l), res)
    return res


def main():
    n, k = na()
    a = na()
    ansl, ansr = 0, 10**9
    while ansl + 1 < ansr:
        now = (ansl + ansr) // 2
        #print(ansl, ansr, now, cut(a, now))
        if cut(a, now) <= k:
            ansr = now
        else:
            ansl = now
    print(ansr)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n,k=map(int, input().split())
a=list(map(int, input().split()))

l=0
r=10**9

while r-l>1:
    mid=(r+l)//2
    cnt=0
    for i in range(n):
        cnt+=(a[i]-1)//mid
    if cnt>k:
        l=mid
    else:
        r=mid
print(r)

Submission status: Accepted

Solution code:
# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
#from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
import math
#from itertools import product, accumulate, combinations, product
#import bisect
#import numpy as np
#from copy import deepcopy
#from collections import deque

INF = 1 << 50


def run():
    N, K = map(int, sysread().split())
    A = list(map(int, sysread().split()))

    l = 0
    r = 10**9
    while int(l) != int(r):
        #print(l, r)
        test = (l + r) / 2
        sum = 0
        for a in A:
            sum += math.ceil(a / test) - 1

        if sum > K:
            l = test
        elif sum < K:
            r = test
        else:# sum == K
            r = test
        if int(r) == r and r-l < 1:
            print(int(r))
            return

    if int(l) == 0:
        print(1)
        return
    if int(l) == l:
        sum = 0
        for a in A:
            sum += math.ceil(a / int(l)) - 1
        if sum == K:
            print(int(l))
            return

    print(int(l)+1)

if __name__ == "__main__":
    run()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import math
import sys
sys.setrecursionlimit(10**6)
INF = 10 ** 9 + 1  # sys.maxsize # float("inf")
MOD = 10 ** 9 + 7


def debug(*x):
    print(*x, file=sys.stderr)


def solve(N, K, AS):
    left = 0
    right = max(AS) + 1

    while left < right - 1:
        mid = (left + right) // 2
        s = sum(a // mid - 1 if a >= mid else 0 for a in AS)
        debug(": ", mid, s)
        if s >= K:
            left = mid
        else:
            right = mid

    x = left
    debug("x: x", x)
    #v = max(a / (a // x + 1 if a >= x else 1) for a in AS)
    # v = max(x + (a % x) / (a // x) if a >= x else a for a in AS)
    queue = []

    leftK = 0
    for i in range(N):
        a = AS[i]
        numDivide = a // x
        leftK += numDivide
        length = a / (numDivide + 1) if numDivide else a
        queue.append((length, numDivide, a))
    debug(": leftK", leftK)
    queue.sort()
    from heapq import heappush, heappop
    for i in range(leftK - K):
        # dec numDivide
        (length, numDivide, a) = heappop(queue)
        numDivide -= 1
        debug(": a, numD", a, numDivide)
        length = a / (numDivide + 1) if numDivide else a
        if numDivide:
            heappush(queue, (length, numDivide, a))
        debug(": length", length)

    return math.ceil(length)
    # return math.ceil(left)


def solve(N, K, AS):
    left = 0
    right = max(AS) + 1

    while left < right - 1:
        mid = (left + right) // 2
        s = sum((a + mid - 1) // mid - 1 if a >= mid else 0 for a in AS)
        debug(": ", mid, s)
        if s > K:
            left = mid
        else:
            right = mid
    return right


def main():
    # parse input
    N, K = map(int, input().split())
    AS = list(map(int, input().split()))
    print(solve(N, K, AS))


# tests
T1 = """
2 3
7 9
"""
TEST_T1 = """
>>> as_input(T1)
>>> main()
4
"""

T2 = """
3 0
3 4 5
"""
TEST_T2 = """
>>> as_input(T2)
>>> main()
5
"""

T3 = """
10 10
158260522 877914575 602436426 24979445 861648772 623690081 433933447 476190629 262703497 211047202
"""
TEST_T3 = """
>>> as_input(T3)
>>> main()
292638192
"""

T4 = """
2 1
4 2
"""
TEST_T4 = """
>>> as_input(T4)
>>> main()
2
"""

T5 = """
2 1
5 2
"""
TEST_T5 = """
>>> as_input(T5)
>>> main()
3
"""

T6 = """
2 1
3 2
"""
TEST_T6 = """
>>> as_input(T6)
>>> main()
2
"""

T7 = """
2 2
3 2
"""
TEST_T7 = """
>>> as_input(T7)
>>> main()
2
"""

T8 = """
2 2
3 1
"""
TEST_T8 = """
>>> as_input(T8)
>>> main()
1
"""

T9 = """
3 1
3 4 5
"""
TEST_T9 = """
>>> as_input(T9)
>>> main()
4
"""

T10 = """
3 2
3 4 5
"""
TEST_T10 = """
>>> as_input(T10)
>>> main()
result
"""


def _test():
    import doctest
    doctest.testmod()
    g = globals()
    for k in sorted(g):
        if k.startswith("TEST_"):
            doctest.run_docstring_examples(g[k], g, name=k)


def as_input(s):
    "use in test, use given string as input file"
    import io
    f = io.StringIO(s.strip())
    g = globals()
    g["input"] = lambda: bytes(f.readline(), "ascii")
    g["read"] = lambda: bytes(f.read(), "ascii")


input = sys.stdin.buffer.readline
read = sys.stdin.buffer.read

if sys.argv[-1] == "-t":
    print("testing")
    _test()
    sys.exit()

main()

Submission status: Accepted

Solution code:
N,K = map(int,input().split())

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

def check(x):
  k = 0
  for a in A:
    k += ((a-1) // x)
  return k <= K

ng,ok = 0, 10**9+1

while ok-ng > 1:
  x = (ok+ng)//2

  if check(x):
    ok = x
  else:
    ng = x

print(ok)

Submission status: Accepted

Solution code:
import math
n,k=map(int,input().split())
log=list(map(int,input().split()))
a=0
b=max(log)
if b==1:
  print(1)
  exit()
c=(a+b)//2
while True:
  div=0
  for i in range(n):
    div+=math.ceil(log[i]/c)-1
  if div<=k:
    b=c
    c=(a+b)//2
  else:
    a=c
    c=(a+b)//2
    
  if c==a or c==b:
    break
print(b)

Submission status: Accepted

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-
n, k = map(int, input().split())
a_list = list(map(int, input().split()))
a_list.sort(reverse=True)
if k == 0:
    print(a_list[0])
else:
    start = 1
    end = a_list[0]
    x = (start + end) // 2 
    while True:
        k_count = 0
        flag = 1
        for a in a_list:
            temp_k = 0
            if a % x == 0:
                temp_k = a // x - 1
            else:
                temp_k = a // x
            if temp_k == 0:
                flag = 1
                break
            k_count += temp_k
            if k_count > k:
                flag = 0
                break
        if flag == 1:
            end = x
        if flag == 0:
            start = x
        next_x = (start + end) // 2
        if next_x == x:
            if flag == 1:
                print(x)
            if flag == 0:
                print(x + 1)
            break
        x = next_x

Submission status: Accepted

Solution code:
import sys,bisect,string,math,time,functools,random,fractions
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
from itertools import permutations,combinations,groupby
rep=range;R=range
def Golf():n,*t=map(int,open(0).read().split())
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in input().split()]
def MI():return map(int,input().split())
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def NI(n):return [int(input()) for i in range(n)]
def NI_(n):return [int(input())-1 for i in range(n)]
def StoLI():return [ord(i)-97 for i in input()]
def ItoS(n):return chr(n+97)
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def Ra():return map(int,open(0).read().split())
def GI(V,E,ls=None,Directed=False,index=1):
    org_inp=[];g=[[] for i in range(V)]
    FromStdin=True if ls==None else False
    for i in range(E):
        if FromStdin:
            inp=LI()
            org_inp.append(inp)
        else:
            inp=ls[i]
        if len(inp)==2:
            a,b=inp;c=1
        else:
            a,b,c=inp
        if index==1:a-=1;b-=1
        aa=(a,c);bb=(b,c);g[a].append(bb)
        if not Directed:g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'#':1,'.':0},boundary=1):
    #h,w,g,sg=GGI(h,w,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0},boundary=1) # sample usage
    mp=[boundary]*(w+2);found={}
    for i in R(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[boundary]+[mp_def[j] for j in s]+[boundary]
    mp+=[boundary]*(w+2)
    return h+2,w+2,mp,found
def TI(n):return GI(n,n-1)
def accum(ls):
    rt=[0]
    for i in ls:rt+=[rt[-1]+i]
    return rt
def bit_combination(n,base=2):
    rt=[]
    for tb in R(base**n):s=[tb//(base**bt)%base for bt in R(n)];rt+=[s]
    return rt
def gcd(x,y):
    if y==0:return x
    if x%y==0:return y
    while x%y!=0:x,y=y,x%y
    return y
def YN(x):print(['NO','YES'][x])
def Yn(x):print(['No','Yes'][x])
def show(*inp,end='\n'):
    if show_flg:print(*inp,end=end)

mo=10**9+7
inf=float('inf')
FourNb=[(-1,0),(1,0),(0,1),(0,-1)];EightNb=[(-1,0),(1,0),(0,1),(0,-1),(1,1),(-1,-1),(1,-1),(-1,1)];compas=dict(zip('WENS',FourNb));cursol=dict(zip('LRUD',FourNb))
l_alp=string.ascii_lowercase
sys.setrecursionlimit(10**9)
read=sys.stdin.buffer.read;readline=sys.stdin.buffer.readline;input=lambda:sys.stdin.readline().rstrip()

########################################################################################################################################################################


def dijkstra(edge,st):
    # edge=[[(v_to,dist_to_v),...],[],...]
    # initialize: def: d=dist(st,i), prev=[previous vertex in minimum path], q[]
    n=len(edge)
    d=[(0 if st==i else inf) for i in range(n)]
    q=[(j,i) for i,j in enumerate(d)]
    heapify(q)
    v=[False]*n
    # calc
    while q:
        dist,cur=heappop(q)
        if v[cur]:
            continue
        v[cur]=True
        for dst,dist in edge[cur]:
            alt=d[cur]+c[cur]
            if alt<d[dst]:
                d[dst]=alt
                heappush(q,(alt,dst))
    return d

class UnionFind:
    def __init__(self, n):
        # 負  : 根であることを示す。絶対値はランクを示す
        # 非負: 根でないことを示す。値は親を示す
        self.table = [-1] * n
 
    def _root(self, x):
        if self.table[x] < 0:
            return x
        else:
            # 経路の圧縮
            self.table[x] = self._root(self.table[x])
            return self.table[x]
 
    def find(self, x, y):
        return self._root(x) == self._root(y)
 
    def union(self, x, y):
        r1 = self._root(x)
        r2 = self._root(y)
        if r1 == r2:
            return
        # ランクの取得
        d1 = self.table[r1]
        d2 = self.table[r2]
        if d1 <= d2:
            self.table[r2] = r1
            if d1 == d2:
                self.table[r1] -= 1
        else:
            self.table[r1] = r2
    
    def __str__(self):
        rt=[i if j<0 else j for i,j in enumerate(self.table)]
        return str(rt)

class Comb:
    def __init__(self,n,mo=10**9+7):
        self.fac=[0]*(n+1)
        self.inv=[1]*(n+1)
        self.fac[0]=1
        self.fact(n)
        for i in range(1,n+1):
            self.fac[i]=i*self.fac[i-1]%mo
            self.inv[n]*=i
            self.inv[n]%=mo
        self.inv[n]=pow(self.inv[n],mo-2,mo)
        for i in range(1,n):
            self.inv[n-i]=self.inv[n-i+1]*(n-i+1)%mo
        return
    
    def fact(self,n):
        return self.fac[n]
        
    def invf(self,n):
        return self.inv[n]

    def comb(self,x,y):
        if y<0 or y>x:
            return 0
        return self.fac[x]*self.inv[x-y]*self.inv[y]%mo



show_flg=False
show_flg=True

ans=0


n,k,*a=map(int,open(0).read().split())

def check(m):
    t=0
    for i in a:
        t+=max(int(i/m+1)-1,0)
    return t>k
        
l,r=0,10**9+10
c=0
while c<100:
    c+=1
    m=(r+l)/2
    l,r,*_=[l,m,r][check(m)::]

print(int(l+0.999999))