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 sys
sys.setrecursionlimit(10**8)
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()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
#from collections import Counter # a = Counter(A).most_common()
#from itertools import accumulate #list(accumulate(A))
import math
 
N, K = mi()
A = li()
 
if K == 0:
    print(max(A))
    exit()
 
left = 0
right = max(A)
 
def count(num):
    cnt = 0
    for i in range(N):
        cnt += math.ceil(A[i] / num) - 1
    return cnt
 
while True:
    mid = (left + right) // 2
    if mid == 0:
        mid += 1
        break
    tmp = count(mid)
    if tmp == K:
        break
    elif tmp > K:
        if left == mid:
            mid = right
            break
        left = mid
    else:
        right = mid
 
if mid == 0 or mid == 1:
    print(mid)
    exit()
 
right = mid
 
while True:
    tmp = count(mid)
    if tmp == K and tmp != count(mid-1):
        print(mid)
        break
    elif tmp == K:
        right = mid
    else:
        if left == mid:
            print(right)
            break
        left = mid
    mid = (left + right) // 2
    if mid == 0:
        print(1)
        break

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**8)
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()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
#from collections import Counter # a = Counter(A).most_common()
from itertools import accumulate #list(accumulate(A))
import math

N, K = mi()
A = li()

if K == 0:
    print(max(A))
    exit()

left = 0
right = max(A)

def count(num):
    cnt = 0
    for i in range(N):
        cnt += math.ceil(A[i] / num) - 1
    return cnt

while True:
    mid = (left + right) // 2
    if mid == 0:
        print(1)
        exit()
    tmp = count(mid)
    if right - left <= 1:
        mid = right
        break
    elif tmp > K:
        left = mid
    else:
        right = mid

right = mid

while True:
    tmp = count(mid)
    if tmp == K and tmp != count(mid-1):
        print(mid)
        break
    elif tmp == K:
        right = mid
    else:
        if left == mid:
            print(right)
            break
        left = mid
    mid = (left + right) // 2
    if mid == 0:
        print(1)
        break

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_s = lambda: readline().rstrip().decode('utf-8')
in_nl = lambda: list(map(int, readline().split()))
in_nl2 = lambda H: [in_nl() for _ in range(H)]
in_map = lambda: [s == ord('.') for s in readline() if s != ord('\n')]
in_map2 = lambda H: [in_map() for _ in range(H)]
in_all = lambda: map(int, read().split())


def main():

    N, K = in_nn()
    A = in_nl()

    def is_ok(x):

        cnt = 0
        for i in range(N):
            q, r = divmod(A[i], x)
            if r == 0:
                q -= 1
            cnt += q

        return cnt <= K

    def bisect(ng, ok):

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

    ans = bisect(0, 10**9 + 1)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

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

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

def cond(upper):
    ans = 0
    for v in a:
        if v <= upper:
            continue
        if v % upper == 0:
            ans += ((v // upper) - 1)
        else:
            ans += v // upper
    return ans <= k

print(bs(max(a), 0, cond))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**8)
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()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
#from collections import Counter # a = Counter(A).most_common()
from itertools import accumulate #list(accumulate(A))
import math

N, K = mi()
A = li()

if K == 0:
    print(max(A))
    exit()

left = 0
right = max(A)

def count(num):
    cnt = 0
    for i in range(N):
        cnt += math.ceil(A[i] / num) - 1
    return cnt

while True:
    mid = (left + right) // 2
    if mid == 0:
        print(1)
        exit()
    tmp = count(mid)
    if right - left <= 1:
        mid = right
        break
    elif tmp > K:
        left = mid
    else:
        right = mid

right = mid

while True:
    tmp = count(mid)
    if right - left <= 1:
        print(right)
        break
    elif tmp == K:
        right = mid
    else:
        left = mid
    mid = (left + right) // 2
    if mid == 0:
        print(1)
        break

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
import math
ng=0
ok=max(a)
center=(ok+ng)//2
while ng+1!=ok:
  counter=0
  for i in range(len(a)):
    counter+=math.ceil(a[i]/center)-1
  if counter>k:
    ng=center
    center=(ok+ng)//2
  else:
    ok=center
    center=(ok+ng)//2
print(ok)

Submission status: Accepted

Solution code:
from math import ceil


def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    a.sort()
    ng = 0
    ok = a[-1]
    while ok - ng > 1:
        mid = (ok + ng) // 2
        cnt = 0
        for i in range(n):
            cnt += (a[i] - 1) // mid
        if cnt <= k:
            ok = mid
        else:
            ng = mid
    print(ceil(ok) if k > 0 else a[-1])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from math import ceil


def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    a.sort()
    ng = 0
    ok = 10 ** 9 + 7
    while ok - ng > 1:
        mid = (ok + ng) // 2
        cnt = 0
        for i in range(n):
            cnt += (a[i] - 1) // mid
        if cnt <= k:
            ok = mid
        else:
            ng = mid
    print(ceil(ok) if k > 0 else a[-1])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
for i in range(1,31):
    if 2**i>=a[-1]+1:
        num=i
        break
ans=2**(num-1)
num1=2**(num-1)
l1=[]
for i in range(num+1):
    cnt=0
    for j in range(n):
        cnt+=-(a[j]//-ans)-1
    num1=num1//2
    if cnt>k:
        ans=min(a[-1],ans+num1)
    else:
        l1.append(ans)
        ans=max(1,ans-num1)
print(min(l1))

Submission status: Accepted

Solution code:
N, M = input().strip().split()
n, k = [int(N), int(M)]
a = list(map(int, input().strip().split()))
le = 0
ri = 10000000000
while ri - le > 1:
    mid = (le + ri)// 2
    num = 0
    for i in a:
        num += (i-1)// mid
    if num <= k:
        ri = mid
    else:
        le = mid
print(ri)

Submission status: Accepted

Solution code:
import math
N,K = map(int,input().split())
A = list(map(int,input().split()))
max_a = max(A)
u = max_a
d = 0
res = 9
max_do = math.ceil(math.log(max_a*10,2))
for _ in range(max_do):
    n = (u + d)/2
    _k = 0
    for _a in A:
        _k += math.ceil(_a/n) - 1
    
    if _k > K:
        d = n
    else:
        u = n
print(math.ceil(n))

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
A=list(map(int,input().split()))
low=0
high=max(A)
while high-low>1:
    mid=(low+high)//2
    cnt=0
    for i in A:
        cnt+=(i-1)//mid
    if cnt>K:
        low=mid
    else:
        high=mid
print(high)

Submission status: Accepted

Solution code:
import math
N, K=map(int, input().split())
A=list(map(int, input().split()))
i=1
j=10**9
while True:
    k=(i+j)//2
    if k>0 and sum([math.ceil(a/k)-1 for a in A])<=K:
        if k==1 or sum([math.ceil(a/(k-1))-1 for a in A])>K:
            print(k)
            break
        else:
            j=k-1
    else:
        i=k+1

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
a = [int(i) for i in input().split()]
l = 0
r = 10**9
while l+1 < r:
    m = (l+r)//2
    cnt = 0
    for i in range(n): cnt += (a[i]+m-1)//m-1
    if cnt > k: l = m
    else: r = m
print(r)

Submission status: Accepted

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

l = 0
r = max(arr)

while l + 1 < r:
    m = (l + r) // 2

    cut = 0
    for x in arr:
        cut += (x - 1) // m

    if cut > k:
        l = m
    else:
        r = m

print(r)

Submission status: Accepted

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

def is_ok(arg):
  cnt = 0
  for i in range(N):
    cnt += (A[i]-1)//arg
  if(cnt <= K):
    return True
  else:
    return False

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

ans = meguru_bisect(0, 10**9)
print(ans)

Submission status: Accepted

Solution code:
import math
def solution(x):
  p = sum([math.ceil(a[i]/x)-1 for i in range(N)])
  return p
def solvance(y,z):
  if z-y <= 1:
    return z
  else:
    w = (y+z)//2
    #print(y,w,z)
    if solution(w) > K:
      return solvance(w,z)
    else:
      return solvance(y,w)

N,K = map(int,input().split())
a = list(map(int,input().split()))
if K == 0:
  print(max(a))
else:
  ansM = (sum(a)//K)+1
  ansm = sum(a)//(K+N)
  ans = solvance(ansm,ansM)
  print(ans)

Submission status: Accepted

Solution code:
import math

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

ng_len = 0
ok_len = 1000000000


def possible_len(length: int, log: list, k: int):
    count = 0
    for i in range(N):
        count += math.ceil(log[i] / length) - 1
    if count <= k:
        return True
    else:
        return False


while ok_len - ng_len > 1:
    mid = (ng_len + ok_len) // 2
    if possible_len(mid, logs, K):
        ok_len = mid
    else:
        ng_len = mid

print(ok_len)

Submission status: Accepted

Solution code:
from math import ceil
 
def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    def is_ok(arg):
    # 条件を満たすかどうか？問題ごとに定義
        B = [int(ceil(a/arg))-1 for a in A]
        #print(arg, B)
        if sum(B) <= K:
            return True
        else:
            return False
 
    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
    
    ans = meguru_bisect(0, int(1e9))
    print(ans)
 
if __name__ == "__main__":
    main()

Submission status: Accepted

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

l = 1
r = 10**9 + 1

import math
while l < r:
    mid = (l + r) // 2
    counter = 0
    for i in range(N):
        if A[i] > mid:
            counter += math.ceil(A[i]/mid) - 1
    if counter <= K:
        r = mid
    else:
        l = mid + 1

print(l)

Submission status: Accepted

Solution code:
# ANSHUL GAUTAM
# IIIT-D

from math import *
from copy import *                      # ll = deepcopy(l)
from heapq import *                     # heappush(hp,x)
from string import *                    # alpha = ascii_lowercase
from random import *                    # l.sort(key=lambda l1:l1[0]-l1[1]) => ex: sort on the basis difference
from bisect import *                    # bisect_left(arr,x,start,end)  => start and end parameters are temporary
from sys import stdin                   # bisect_left return leftmost position where x should be inserted to keep sorted
from sys import maxsize                 # minn = -maxsize
from operator import *                  # d = sorted(d.items(), key=itemgetter(1))
from itertools import *                 # pre = [0] + list(accumulate(l))
from decimal import Decimal             # a = Decimal(a)    # use this for math questions
from collections import Counter         # d = dict(Counter(l))
from collections import defaultdict     # d = defaultdict(list)

'''
2 3
7 9
'''

def f(l,k,x):
    cuts = 0
    for i in l:
        cuts += (ceil(i/x)-1)
    return cuts <= k

def solve(l,k):
    n = len(l)
    if(k == 0):
        return max(l)
    lo,hi = 1,max(l)
    l.sort(reverse=True)
    ans = max(l)
    while(lo <= hi):
        mid = (lo + hi) >> 1
        if(f(l,k,mid)):
            hi = mid - 1
            ans = min(ans,mid)
        else:
            lo = mid + 1
    return ans

N,K = list(map(int, stdin.readline().rstrip().split()))
l = list(map(int, stdin.readline().rstrip().split()))
ans = solve(l,K)
print(ans)

Submission status: Accepted

Solution code:
def ceil(X, Y):  # 天井関数 ceil(X/Y) Y>1
    return (X + Y - 1) // Y


def binary(N):  # 二分探索 # N:探索要素数
    l, r = -1, N
    while r - l > 1:
        if (l + r) // 2 == 0:
            return 1
        cnt = sum(ceil(ai, (l + r) // 2) - 1 for ai in a)
        if cnt <= k:  # 条件式を代入
            r = (l + r) // 2
        else:
            l = (l + r) // 2
    return r


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

print(binary(max(a)))

Submission status: Accepted

Solution code:
import sys

import numba as nb
import numpy as np

input = sys.stdin.readline


@nb.njit("i8(i8,i8[:],i8)", cache=True)
def binary_search(N, A, K):
    """Meguru type binary search"""
    ng = 0
    ok = 10 ** 9 + 1

    def is_ok(N, A, K, min_v):
        Q = A // min_v
        R = A % min_v
        count = np.sum(Q + (R > 0)) - N
        if count <= K:
            return True
        else:
            return False

    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if is_ok(N, A, K, mid):
            ok = mid
        else:
            ng = mid

    return ok


def main():
    N, K = map(int, input().split())
    A = np.array(input().split(), dtype=np.int64)

    ans = binary_search(N, A, K)

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N, M = input().strip().split()
n, k = [int(N), int(M)]
a = list(map(int, input().strip().split()))
le = 0
ri = 10000000000
while ri - le > 1:
    mid = (le + ri) // 2
    num = 0
    for i in a:
        num += (i-1) // mid
    if num <= k:
        ri = mid
    else:
        le = mid
print(ri)

Submission status: Accepted

Solution code:
import math
import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))


INF=10**20
def main():
    N,K=mi()
    A=list(mi())

    A.sort(reverse=True)
    l = 0
    r = A[0]

    while r-l > 1:
        # print("l,r:",l,r)
        mid = (r+l)//2
        
        count = 0

        for i in range(N):
            if mid < A[i]:
                count += math.ceil(A[i]/mid)-1
        
        # print(mid,count)
        if count > K:
            l = mid
        else:
            r = mid
    
    print(r)

    

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import math

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

def isPossible(X):
    global N, K, A

    cuts = 0
    for i in range(N):
        cuts += math.ceil(A[i]/X) - 1
    
    return cuts <= K

minVal = 0
maxVal = max(A)

while math.ceil(minVal) != math.ceil(maxVal):
    if isPossible((maxVal + minVal) / 2):
        maxVal = (maxVal + minVal) / 2
    else:
        minVal = (maxVal + minVal) / 2

print(math.ceil(maxVal))

Submission status: Accepted

Solution code:
from math import ceil

def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    def is_ok(arg):
    # 条件を満たすかどうか？問題ごとに定義
        B = [int(ceil(a/arg))-1 for a in A]
        #print(arg, B)
        if sum(B) <= K:
            return True
        else:
            return False

    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
    
    ans = meguru_bisect(0, int(1e20))
    print(ans)

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:
  m = (r+l) // 2
  count = 0
  for i in A:
    if i > m:
      count += i // m
      
  if count > K:
    l = m
  else:
    r = m
    
print(r)

Submission status: Accepted

Solution code:
def mbisect(ok, ng):
    while abs(ok - ng) > 1:
        mid = (ok + ng) // 2
        if check(mid):
            ok = mid
        else:
            ng = mid
    return ok


def check(mid):
    if mid == 0:
        return False
    cnt = 0
    for i in a:
        cnt += (i + mid - 1) // mid - 1
    return cnt <= k


n, k = map(int, input().split())
a = tuple(map(int, input().split()))
print(mbisect(10 ** 9, -1))

Submission status: Accepted

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

def check(l):
    t = 0
    for i in a:
        t += -(-i // l) - 1
    return t <= k

l, r = 0, 10 ** 9 + 1
while r - l > 1:
    mid = (l + r) // 2 + (l + r) % 2
    if check(mid):
        r = mid
    else:
        l = mid

print(r)

Submission status: Accepted

Solution code:
def BC(A,K):
    """2分探索によって,x未満の要素の個数を調べる.

    A:リスト
    x:調べる要素
    sort:ソートをする必要があるかどうか(Trueで必要)
    equal:Trueのときはx"未満"がx"以下"になる
    """
    N=max(A)+1
    
    L,R=0,N
    while R-L>1:
        C=L+(R-L)//2

        M=0
        for a in A:
            M+=(a+C-1)//C-1

        if M<=K:
            R=C
        else:
            L=C
    return R


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

Submission status: Accepted

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

l = 1
r = 10**9 + 1

while l < r:
    mid = (l + r) // 2
    counter = 0
    for i in range(N):
        if A[i] > mid:
            counter += A[i] // mid
    if counter <= K:
        r = mid
    else:
        l = mid + 1

print(l)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
import math

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

ng_len = 1
ok_len = 1000000000


def possible_len(length: int, log: list, k: int):
    count = 0
    for i in range(N):
        count += math.ceil(log[i] / length) - 1
    if count <= k:
        return True
    else:
        return False


while ok_len - ng_len > 1:
    mid = (ng_len + ok_len) // 2
    if possible_len(mid, logs, K):
        ok_len = mid
    else:
        ng_len = mid

if possible_len(ng_len, logs, K):
    print(ng_len)
else:
    print(ok_len)

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()))
    l = 1
    r = max(a)
    while l < r:
        m = (l+r)//2
        cnt = 0
        for x in a:
            cnt += (x-1)//m
        if cnt > k: l = m+1
        else: r = m
    print(r)
    


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from math import ceil

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

l = 0
r = 10**9
ans = 0
while l+1 < r:  
  m = (l+r)//2  
  c = 0
  for a in A:
    c += ceil(a/m)-1
  if c <= k:
    ans = min(ans,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()))
l = 0
r = 10 ** 9

while r-l > 1 :
    m = (l+r)//2 
    b = list(map(lambda x: -(-x//m) - 1 ,a))
    ans = sum(b)
    if ans <= k :
        r = m
    else :
        l = m

print(r)

Submission status: Accepted

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


def read():
    N, K = map(int, input().strip().split())
    A = list(map(int, input().strip().split()))
    return N, K, A


def solve(N, K, A):
    ng = 0
    ok = max(A)
    while abs(ok-ng) > 1:
        mid = (ok+ng) // 2
        k = sum([(a-1) // mid for a in A])
        if k <= K:
            ok = mid
        else:
            ng = mid
    return ok


if __name__ == '__main__':
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print("%s" % str(outputs))

Submission status: Accepted

Solution code:
import sys
import math

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

tin=lambda : map(int, input().split())
lin=lambda : list(tin())
mod=1000000007

#+++++

def cc(al, v_max, k):
	for vl in al:
		if vl <= v_max:
			return True
		k -= ((vl + v_max- 1) // v_max) - 1
		#pa((k, -(-v // v_max)))
		if k < 0:
			return False
	return True
		

def main():
	#a = int(input())
	n, k = tin()
	#s = input()
	al = lin()
	al.sort(reverse = True)
	#print(al)
	ok = al[0]
	ng = 0
	while ok - ng > 1:
		mid = (ok + ng)//2
		ii=cc(al, mid, k)
		#pa((mid,ii))
		if ii:
			ok = mid
		else:
			ng = mid
	#pa(ok)
	print(ok)
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Accepted

Solution code:
from math import ceil

def isOK(length):
  ans = 0
  for a in A:
    ans += ceil(a / length) - 1
  return ans <= k

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

start, end = 0, 10**9 + 1
while True:
  mid = (start + end) // 2
  if mid == 1:
    print(mid)
    exit()
  prev = mid - 1
  if isOK(mid):
    if isOK(prev):
      end = mid
    else:
      print(mid)
      exit()
  else:
    start = mid

Submission status: Accepted

Solution code:
import sys
import math
n,k = map(int,input().split())
a = list(map(int,input().split()))
if k ==0:
  print(max(a))
  sys.exit()
def check(t):
  ans = 0
  if t==0:
    return False
  for aa in a:
    if aa > t:
      ans += aa//t
  return ans <= k
max = 10**9+1
min = 0
while max-min>1:
  mid = (max+min)//2
  if check(mid):
    max = mid
  else:
    min = mid
print(math.ceil(max))

Submission status: Accepted

Solution code:
import sys
import heapq
import math


def input():
    return sys.stdin.readline().rstrip()


def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    ok = max(A)
    ng = 0

    while abs(ok - ng) > 1:
        mid = abs(ok + ng) // 2
        count = 0
        for i in range(N):
            count += math.ceil(A[i] / mid)-1
        if count <=K:
            ok = mid
        else:
            ng = mid

    print(ok)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

def possible(x):
    count = 0
    for a in A:
        if a <= x:
            return True
        count += int(ceil(a/x)) - 1
        if count > K:
            return False
    return True

def solve():
    lo, hi = 0, A[0]
    while lo < hi-1:
        mi = (hi + lo) // 2
        if possible(mi):
            hi = mi
        else:
            lo = mi
    return hi

if __name__ == "__main__":
    print(solve())

Submission status: Accepted

Solution code:
import sys

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

if k == 0:
    print(max(a))
    sys.exit()

def check(t):
    if t == 0:
        return False
    ans = 0
    for ai in a:
        if ai > t:
            ans += ai // t
    return ans <= k

l = 0
r = 10 ** 9 + 1

while r - l > 1:
    mid = (r + l) // 2
    if check(mid):
        r = mid
    else:
        l = mid

if check(l):
    print(l)
else:
    print(r)

Submission status: Accepted

Solution code:
def solve(A,N,K):
    ans_max,ans_min = max(A),1

    while True:
        if cutable(A,N,K,(ans_max+ans_min)//2):
            if ans_max > (ans_max+ans_min)//2:
                ans_max = (ans_max+ans_min)//2
            else:
                return ans_max
        else:
            if ans_min < (ans_max+ans_min)//2:
                ans_min = (ans_max+ans_min)//2
            else:
                return ans_max

def cutable(A,N,K,div):
    #K回までの切断で全部を長さdiv以下にできるかどうか
    cnt = 0
    for i in range(N):
        cnt += A[i]//div
        if A[i] % div == 0:
            cnt -= 1
        if cnt > K:
            return False

    return True

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

    ans = solve(A,N,K)
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from heapq import heapify,heappop,heappush

def solve(A,N,K):
    ans_max,ans_min = max(A),1

    while True:
        if cutable(A,N,K,(ans_max+ans_min)//2):
            if ans_max > (ans_max+ans_min)//2:
                ans_max = (ans_max+ans_min)//2
            else:
                return ans_max
        else:
            if ans_min < (ans_max+ans_min)//2:
                ans_min = (ans_max+ans_min)//2
            else:
                return ans_max

def cutable(A,N,K,div):
    #K回までの切断で全部を長さdiv以下にできるかどうか
    cnt = 0
    for i in range(N):
        cnt += A[i]//div
        if A[i] % div == 0:
            cnt -= 1
        if cnt > K:
            return False

    return True

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

    ans = solve(A,N,K)
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# N,M = map(int,sys.stdin.readline().split())
# a = tuple(map(int,sys.stdin.readline().split())) # single line with multi param
# a = tuple(int(sys.stdin.readline()) for _ in range(N)) # multi line with single param
# a = tuple(tuple(map(int,sys.stdin.readline().rstrip().split())) for _ in range(N)) # multi line with multi param
# s = sys.stdin.readline().rstrip()
# N = int(sys.stdin.readline())
INF = float("inf")
import sys,collections,heapq,math

N,K = map(int,sys.stdin.readline().split())
a = list(map(int,sys.stdin.readline().split())) # single line with multi param
a.sort(reverse=True)

ng = 0
ok = a[0]

def isOK(v):
    # within range
    # return key <= a[index]
    k = K
    i = 0
    while k >= 0 and i < N:
        #print("?",v,i,a[i],k,math.ceil(a[i] / v) -1,k - (math.ceil(a[i]/v) - 1))
        k = k - (((a[i]+v-1)//v) - 1)
        #k = k - (math.ceil(a[i]/v) - 1)
        i += 1
    return k >= 0

while abs(ng-ok) > 1:
    mid = (ok+ng)//2
    #print(mid,isOK(mid))
    if isOK(mid):#ok condition?
        ok = mid #move ok
    else:
        ng = mid
#294924427
print(math.ceil(ok))

# a = [[-b,b,1] for b in tuple(map(int,sys.stdin.readline().split()))] # single line with multi param
# heapq.heapify(a)# a == [1,2,3]
# for _ in range(K):
#     _,ori,di = heapq.heappop(a)
#     heapq.heappush(a, [-(ori)/(di+1),ori,di+1])
# print(math.ceil(-a[0][0]))

Submission status: Accepted

Solution code:
import heapq
import bisect

n,k=map(int, input().split())
A=[int(i) for i in input().split()]
ng=0
ok = max(A)
while(ng+1!=ok):
    mid = (ok+ng)//2
    ans = 0
    for i in A:
        ans += 0--i//mid-1
    if(ans<=k):
        ok = mid
    else:
        ng = mid
print(ok)

Submission status: Accepted

Solution code:
import sys
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり

N,K = MI()
A = LI()

left = 0
right = max(A)  # 可能
while left + 1 < right:
    mid = (left + right)//2
    if sum((A[i]+mid-1)//mid - 1 for i in range(N)) <= K:
        right = mid
    else:
        left = mid
print(right)