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:
#!/usr/bin/env python3
# 回の決め打ち二分探索
import math


def solve(n):
    cnt = 0
    for i in a:
        if i % n == 0:
            cnt += i // n - 1
        else:
            cnt += i // n
    if cnt <= k:
        return True  # k以下の分割で長さn いかにできる
    else:
        return False


n, k = map(int, input().split())
a = [int(_) for _ in input().split()]
ng = 0  # 長さ1にはできる
ok = 10 ** 9 + 1
while abs(ok - ng) > 1:
    mid = (ok + ng) // 2
    if solve(mid):
        ok = mid
    else:
        ng = mid
print(ok)

Submission status: Accepted

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

from math import ceil

def f(length):
  rtn = 0
  for i in range(n):
    rtn += ceil(a[i]/length) - 1
  return rtn

if f(1) == 0:
  print(1)
else:
  while ok - ng > 1:
    mid = (ok + ng)//2
    if f(mid) <= k:
      ok = mid
    else:
      ng = mid

  if f(ng) > k:
    print(ok)
  else:
    print(ng)

Submission status: Accepted

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

#全ての丸太を長さt以下にするのに必要な切断数が
#k以下であるような最大のtを求める
ok=max(A)
ng=0

def isok(t):
  res=0
  for i in range(N):
    res+=A[i]//t-(A[i]%t==0)
  return res<=K

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

print(ok)

Submission status: Accepted

Solution code:
import math
import sys
input = sys.stdin.readline
INF = float("inf")


def isOK(m, K, arr):
    cnt = 0
    for a in arr:
        if a > m:
            cnt += a // m
    return cnt <= K


def binary_search(ok, ng, K, arr=[]):
    while abs(ok - ng) > 1:
        mid = (ok + ng) // 2
        if isOK(mid, K, arr):
            ok = mid
        else:
            ng = mid
    return ok


# 処理内容
def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    
    ok = 10**9
    ng = 0
    ans = binary_search(ok, ng, K, A)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
I=lambda:list(map(int,input().split()))
n,k=I()
l=I()
low=1
high=max(l)
while low<high:
	mid=(low+high)//2
	temp=0
	for i in l:
		temp+=(i//mid)-(i%mid==0)
	if temp>k:
		low=mid+1
	else:
		high=mid
print(low)

Submission status: Accepted

Solution code:
import sys
from bisect import bisect_right
from math import ceil
def input(): return sys.stdin.readline().strip()


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

    left = 0
    right = A[-1]
    while right - left > 1:
        mid = (left + right) // 2
        idx = bisect_right(A, mid)
        cnt = 0
        for i in range(idx, N):
            if A[i] % mid == 0:
                cnt += A[i] // mid - 1
            else:
                cnt += A[i] // mid
        if cnt > K:
            left = mid
        else:
            right = mid
    print(ceil(right))



if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
alist = list(map(int, input().split()))
import math
K += N
sum_ = sum(alist)
ideal_denom = [(K / sum_) * a for a in alist]
min_denom = [math.floor(i_d) if math.floor(i_d) != 0 else 1 for i_d in ideal_denom]
max_denomed_alist = [a/m_d for a, m_d in zip(alist, min_denom) ]
min_denomed_alist = [a/(m_d+1) for a, m_d in zip(alist, min_denom)]

num_replace = K - sum(min_denom)

max_denomed_alist.sort(reverse=True)
ans = math.ceil(max_denomed_alist[num_replace])
 

print(ans)

Submission status: Accepted

Solution code:
N, K = map(int,input().split())
A = [int(x) for x in input().split()]

l = 0
r = max(A) + 1

while(l+1<r):
    m = (l+r)//2
    count = 0
    for a in A:
        count += (a-1) // m
    
    if count > K:
        l = m
    else:
        r = m
print(r)

Submission status: Accepted

Solution code:
import math
n, k = map(int, input().split())
a = list(map(int, input().split()))
def solve(x):
    kk = k
    for i in a:
        kk -= (i+x-1)//x - 1
    return kk>=0

ok = 10**9
ng = 0
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 main():
    N, K = map(int, input().split())
    As = list(map(int, input().split()))

    l = 0
    r = 10**9

    while (r - l) >= 10**(-6):
        m = (l + r) / 2
        t = 0
        for A in As:
            t += math.ceil(A / m - 1)
            if t > K:
                break

        if t <= K:
            l, r = l, m
        else:
            l, r = m, r

    print(math.ceil(l))

main()

Submission status: Accepted

Solution code:
import heapq
from decimal import *
import math

def binary_search(left: int, right: int, check_func, search_max:bool=False):
    # ok と ng のどちらが大きいかわからないことを考慮
    while abs(right - left) > 1:
        mid = (left + right) // 2
    
        if check_func(mid) ^ search_max:
            right = mid
        else:
            left = mid

    return left if search_max else right

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

    def isOK(x):
        b = sum([(a - 1) // x for a in A])

        return b <= K

    ans = binary_search(0, 10 ** 9, isOK)
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N, K = [int(_) for _ in input().split()]
A = [int(_) for _ in input().split()]

def judge(x):
    k = 0
    for a in A:
        v = a // x
        if a % x == 0:
            v -= 1
        k += v
    return k <= K

low = 1
high = max(A)

A.sort()

while low < high - 1:
    mid = (low + high) // 2
    if judge(mid):
        high = mid
    else:
        low = mid

if judge(low):
    print(low)
else:
    print(high)

Submission status: Accepted

Solution code:
from math import *
def isok(x):
    res=0
    for i in range(N):
        if A[i]<=x:
            continue
        res+=floor(A[i]/x)
    if res<=K:
        return True
    else:
        return False

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

ng,ok=0,10**10

while(ok-ng>1):
    mid=(ok+ng)//2
    if isok(mid):
        ok=mid#最大をmid以下にするのが可能かどうか
    else:
        ng=mid
print(ok)

Submission status: Accepted

Solution code:
n,k=map(int, input().split())
a = list(map(int, input().split()))
a=sorted(a,reverse=True)
if k==0:
    print(max(a))
    exit()
import math
lo=0
hi=10**9
oldmid=0
while True:
    mid=(hi+lo)/2
    cnt=0
    for i in range(n):
        cnt+=round(a[i]/mid-0.5)
    if cnt>k:
        lo=mid
    elif cnt<=k:
        hi=mid
    if oldmid-0.000001<=(hi+lo)/2<=oldmid+0.000001:
        print(min(math.ceil(lo), max(a)))
        break
    oldmid=mid

Submission status: Accepted

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

OK = 10**9
NG = 0

while OK - NG > 1:
    ans = 0
    mid = (OK+NG)//2
    for a in A:
        ans += (a-0.1)//mid
    if ans > K:
        NG = mid
    else:
        OK = mid
print(OK)

Submission status: Accepted

Solution code:
import math
import heapq
def main():

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

    l, r = 1, max(A)
    valid = max(A)

    while l <= r:
        m = (l+r) // 2
        count = 0
        for v in A:
            count += (v-1) // m
        if count <= K:
            r = m-1
            valid = min(valid, m)
        else:
            l = m+1

    ans = max(A)
    for u in [valid+1, valid, max(1,valid-1)]:
        count = 0
        for v in A:
            count += (v-1) // u
        if count <= K:
            ans = u
    return ans

if __name__ == '__main__':
    print(main())

Submission status: Accepted

Solution code:
def ceil(n, m):
    return -(-n // m)

# K回のカットで長さlにできるかどうか
def possible(l, K):
    cut = 0
    if l <= 0:
        return False
    for i in range(N):
        cut += ceil(A[i], l) - 1
        if cut > K:
            return False
    return True

N, K = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
L = sum(A)

ng = (L // (N + K)) - 1  # min -1
ok = max(A)

while ok - ng > 1:
    mid = (ok + ng) // 2
    if possible(mid, K):
        ok = mid
    else:
        ng = mid

print(ok)

Submission status: Accepted

Solution code:
import heapq
import math

n, k = map(int, input().split())
a = list(map(int, input().split()))
a.sort(reverse=True)
if k == 0:
    print(a[0])
    exit(0)
mean_a = sum(a) / k
q = []
for aa in a:
    d = max(math.floor(aa / mean_a), 1)
    q.append((-aa/d, d))
    k -= (d-1)
heapq.heapify(q)

for _ in range(k):
    aa, n = heapq.heappop(q)
    heapq.heappush(q, (aa*n/(n+1), n+1))

ans, _ = heapq.heappop(q)
print(math.ceil(-ans))

Submission status: Accepted

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

lo = 1
hi = max(a)


def ceildiv(a, b):
    return (a + b - 1) // b

def ok(x):
    cuts = 0
    for log in a:
        cuts += ceildiv(log, x) - 1

    if cuts <= k:
        return True

    return False

while lo < hi:
    mid = (lo + hi) // 2

    if ok(mid):
        hi = mid
    else:
        lo = mid + 1

print(lo)

Submission status: Accepted

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

def p(length): # p = 1 => その長さに切り分けることは可能
    if length == 0:
        return 1

    tmp = 0
    for a in A:
        if a % length == 0:
            tmp += (a // length) - 1
        else:
            tmp += a // length
        if tmp > K:
            return 0
    
    # print("length", length, "tmp ", tmp)
    
    return 1
    

def bin_search(arr): #答え(最長の丸太の最小値)として取りうる最大値
    lb = 0
    ub = 1000000000

    while ub - lb > 1:
        mid = (ub + lb) // 2
        if p(mid) == 1:
            ub = mid
        else:
            lb = mid
    
    return lb

def just(num):
    if num == 0:
        return 0
        
    tmp = 0
    for a in A:
        if a % num != 0:
            return 0
        else:
            tmp += a // num
    if tmp != K:
        return 0
    else:
        return 1

ans_tmp = bin_search(A)
if just(ans_tmp) == 1:
    print(ans_tmp)
else:
    print(ans_tmp + 1)

Submission status: Accepted

Solution code:

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

ub = 10 ** 9 + 7
lb = 0
while ub - lb > 1:
    mid = (ub + lb) // 2

    res = 0
    for v in X:
        res += (v - 1) // mid

    if res <= K:
        ub = mid
    else:
        lb = mid

print(ub)

Submission status: Accepted

Solution code:
from math import ceil
def C(x):
  cnt = 0
  for i in range(n):
    cnt += ceil(a[i] / x) - 1
  if cnt > k:
    return False
  else:
    return True
  
n, k = map(int, input().split())
a = list(map(int, input().split()))
lb = 0
ub = 1000000000
while ub - lb > 1:
  mid = (lb + ub) // 2
  if C(mid):
    ub = mid
  else:
    lb = mid
print(ub)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop, heapify

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


def check(x):
    # 最長の丸太をx以下にできるか
    # 任意の丸太をx以下にできるか
    cnt = sum([(ai - 1) // x for ai in a])
    return cnt <= k


lb = 0  # False
ub = max(a)  # True
while ub - lb > 1:
    mid = (ub + lb) // 2
    # print(mid, check(mid))
    if check(mid):
        ub = mid
    else:
        lb = mid

print(ub)

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd
from itertools import accumulate, permutations, combinations, product, groupby, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce
from decimal import Decimal, ROUND_CEILING
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7
 
N, K = MAP()
A = LIST()

l = 0
r = 10**9+1
while l+1 != r:
    m = (l+r)//2
    cnt = 0
    for L in A:
        cnt += 0--L//m-1
        if cnt > K:
            ret = False
            break
    else:
        ret = True

    if ret:
        r = m
    else:
        l = m
print(l+1)

Submission status: Accepted

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


def C(x):
    return sum([max((Ai + x - 1) // x - 1, 0) for Ai in A])


A.sort()
left = 1
right = A[-1]
while left + 1 < right:
    mid = (left + right) // 2
    S = C(mid)
    if S <= K:
        right = mid
    else:
        left = mid
print(left if C(left) <= K else right)

Submission status: Accepted

Solution code:
from bisect import bisect_left,bisect
import math

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

m = 0
M = max(A) + 1

while M - m > 1:
  temp = (M + m) // 2
  L = bisect(A, temp)
  cnt = 0
  for i in range(L, N):
    p, q = divmod(A[i], temp)
    if q == 0:
      cnt += p-1
    else:
      cnt += p
  if cnt > K:
    m = temp
  else:
    M = temp

print(M)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
I = lambda : list(map(int,input().split()))

n,k=I()
l=I()
lo=1;hi=max(l)
while lo<hi:
	md=(lo+hi)//2
	ct=0
	for i in range(n):
		ct+=l[i]//md-(l[i]%md==0)
	if ct<=k:
		hi=md
	else:
		lo=md+1
print(lo)

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

import math

n,k = na()
a = na()

def is_ok(arg):
    if arg == 0: return False
    j = 0
    for i in a:
        j += math.ceil(i/arg)-1
        if j > k:
            return False
    return True

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

print(ok)

Submission status: Accepted

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

def test(m):
    if m <= 0:
        return False
    needed = 0
    for a in A:
        needed += (a-1)//m
        if needed > K:
            return False
    return True

lb = 1
ub = max(A)

while True:
    m = (lb + ub) // 2
    if test(m):
        if test(m-1):
            ub = m - 1
        else:
            print(m)
            exit()
    else:
        lb = m + 1

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**8)
import math
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return [LIST() for _ in range(n)]
def NSTR(n): return [input() for _ in range(n)]


INF = float("inf")
MOD = 10**9 + 7


def main():
    N, K = MAP()
    A = LIST()

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

    # X決め打ち二分探索
    left = 0
    right = 10**9+7
    while right - left > 1.0e-6:
        mid = (right + left) / 2
        count = 0
        for a in A:
            count += int(math.ceil(a / mid))-1
        # print(mid, count)
        if count <= K:
            right = mid
        else:
            left = mid
    # print(left, right)
    print(int(math.ceil(left)))

    # mid = int(math.ceil(left))
    # count = 0
    # for a in A:
    #     count += int(math.ceil(a/mid)-1)
    # print(count <= K)

    return


if __name__ == '__main__':
    main()

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):
    if N == 1:
        if K == 0:
            return A[0]
        else:
            return math.ceil(A[0] / (K+1))
    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 math
from heapq import heappop
import heapq
N, K = map(int, input().split())
A = list(map(int, input().split()))

l = 0
r = max(A)+1

while(l+1 < r):
    m = (l+r)//2
    tmp = 0
    for a in A:
        tmp += math.ceil(a / m)-1
    if tmp <= K:
        r = m
    else:
        l = m

print(r)

Submission status: Accepted

Solution code:
n,k = map(int, raw_input().split())
ais = map(int, raw_input().split())

def p(m,ais,k):
	t = [ m, ais, k]
	for ai in ais:
		if ai > m:
			k-= ai / m
	return k >=0

lo,hi = 1, max(ais)

while(lo < hi):
	med = (lo + hi)/2
	if p(med, ais, k):
		hi = med
	else:
		lo = med + 1

print lo

Submission status: Accepted

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

def calc(n):
    num = K
    for a in A:
        s = max(a // n, 1)
        for cnt in range(s, a):
            if a / cnt <= n:
                num -= cnt - 1
                break
        if num < 0:
            return False
    return True


while end - start > 1:
    mid = (end + start) // 2
    if calc(mid):
        end = mid
    else:
        start = mid

print(end)

Submission status: Accepted

Solution code:
def is_ok(mid):   
    global N, K, A
    cnt = 0
    flag = True
    for i in range(N):
        if A[i] <= mid:
            break
        if cnt + A[i] // mid > K:
            flag = False
            break
        cnt += A[i] // mid
    if flag:
        return True
    return False

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

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

Submission status: Accepted

Solution code:
import math

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
    count = 0
    for i in range(n):
        if A[i] > mid:
            count += math.ceil(A[i]//mid)

    if count <= k:
        r = mid
    else:
        l = mid+1


print(l)

Submission status: Accepted

Solution code:
import copy
import math

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

ub = 10**9
lb = 0

while ub - lb > 10**-6:
    x = (ub + lb) / 2
    cnt = 0
    for i in a:
        cnt += math.ceil(i/x)
    if cnt <= n+k:
        ub = copy.deepcopy(x)
    else:
        lb = copy.deepcopy(x)
ans = round(ub, 6)
print(math.ceil(lb))

Submission status: Accepted

Solution code:
import math
def is_ok(mid,k):
  cnt=0
  for i in a:
    cnt+=max(int((i-0.1)/mid),0)
  if cnt<=k:return 1
  else:return 0
n,k=map(int,input().split())
a=sorted(list(map(int,input().split())))
ng=0
ok=a[-1]
while abs(ng-ok)>0.0001:
  mid=(ng+ok)/2
  if is_ok(mid,k):ok=mid
  else:ng=mid
print(math.ceil(ok))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from math import ceil

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


def f(p):
    c = 0
    for x in a:
        c += x // p
    return c


ok, ng = 0, max(a) + 1
while abs(ok - ng) > 3e-6:
    m = (ok + ng) / 2
    if f(m) > k:
        ok = m
    else:
        ng = m
print(ceil(ok))

Submission status: Accepted

Solution code:
import math

LI = lambda: list(map(int, input().split()))

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


def judge(x):
    k = 0
    for a in A:
        if a <= x:
            continue
        if a % x == 0:
            k += a // x - 1
        else:
            k += a // x
    if k <= K:
        return True
    else:
        return False


def solve():
    left, right = 0, max(A)
    while right - left > 1:
        x = (left + right) // 2
        if judge(x):
            right = x
        else:
            left = x
    return right


def main():
    ans = solve()
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#

import sys
from math import ceil
input=sys.stdin.readline

def main():
    N,K=map(int,input().split())
    A=list(map(int,input().split()))
    aveA=sum(A)/N
    d=K/N
    K_i=[int(A[i]/aveA*d) for i in range(N)]
    dA=[A[i]/(K_i[i]+1) for i in range(N)]
    res=K-sum(K_i)
    b=[]
    for i in range(N):
        b.append([dA[i],i])
    b.sort(reverse=True)
    now=0
    for i in range(res):
        K_i[b[now][1]]+=1
        dA[b[now][1]]=A[b[now][1]]/(K_i[b[now][1]]+1)
        if dA[b[now][1]]<b[now+1][0]:
            now+=1
    
    maxi=dA.index(max(dA))
    print(ceil(A[maxi]/(K_i[maxi]+1)))
    
    
    
if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
import sys
import math

N, K = map(int, sys.stdin.readline().strip().split())
A = list(map(int, sys.stdin.readline().strip().split()))

left = 0  # 出来ない長さ
right = 10 ** 9 + 1  # 出来る長さ


def judge(length, num_cut):
    cut = 0
    for a in A:
        if a > length:
            cut += math.ceil(a / length) - 1

    if cut <= num_cut:
        return True

    return False


while right - left > 1:
    mid = (left + right) // 2
    # print(f'right: {right}, left: {left}, mid: {mid}')

    if judge(mid, K):
        right = mid
    else:
        left = mid

print(right)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
def f(x):
    global a,n,k
    if x==0:
        return 10**10
    ret=0
    for i in range(n):
        #print(-((-a[i])//x))
        ret+=(-((-a[i])//x)-1)
    return ret

l,r=0,10**10
while l+1<r:
    x=l+(r-l)//2
    if f(x)<=k:
        r=x
    else:
        l=x

print(r)
#print(f(r))

Submission status: Accepted

Solution code:
from math import ceil

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

def flag(upper):
    c = 0
    for a in A:
        c += ceil(a / upper) - 1
        if c > k:
            return False
    return True

def main():
    A.sort(reverse=True)
    low = 1
    high = A[0]
    while low < high:
        mid = (low + high) // 2
        if flag(mid):
            high = mid
        else:
            low = mid + 1
    print(high)
    return

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#region bcf
# code section by Barry Fam
#
# pylint: disable= reimported
#region logsearch.py
import math as m


def binary_search_int(f, start, stop):
    """
    Binary search for the point at which f() becomes false

    f() may be evaluated at the points in [start, stop) half-open
    The return value will be in the range [start, stop] inclusive

    f() must be always true to the left of some point, and always false to the right

    >>> f = lambda x: x <= 50
    >>> binary_search_int(f, 40, 91)
    51
    >>> binary_search_int(f, 20, 31)
    31
    >>> binary_search_int(f, 60, 81)
    60
    """
    assert start < stop

    left, right = start, stop
    while left < right:
        mid = (left + right)//2
        if f(mid):
            left = mid+1
        else:
            right = mid

    return right


def binary_search_float(f, left, right, rel_tol=1e-09, abs_tol=0.0):
    """
    Binary search for the point at which f() becomes false

    f() must be always true to the left of some point, and always false to the right

    Note: If the return may be close to 0, set abs_tol to avoid excessive/infinite iteration

    >>> f = lambda x: x < 3.5
    >>> _ = binary_search_float(f, 0, 10)
    >>> round(_, 6)
    3.5
    """
    assert left <= right

    while not m.isclose(left, right, rel_tol=rel_tol, abs_tol=abs_tol):
        mid = (left + right)/2
        if f(mid):
            left = mid
        else:
            right = mid

    return right


def ternary_search_int(f, start, stop):
    """
    Ternary search for the maximum point of f()

    df/dx must be always positive to the left of some point, and always negative to the right

    >>> f = lambda x: -(x-42)**2
    >>> ternary_search_int(f, 0, 100)
    42
    """
    assert start < stop

    invphi2 = (3-m.sqrt(5)) / 2

    a, d = start, stop-1
    b = a + round(invphi2 * (d-a))
    c = b + m.ceil(invphi2 * (d-b))
    fb = f(b)
    fc = f(c)

    while True:
        if fb < fc:
            if c == d: return d
            a = b+1
            b, fb = c, fc
            c = b + m.ceil(invphi2 * (d-b))
            fc = f(c)
        else:
            if a == b: return a
            d = c-1
            c, fc = b, fb
            b = c - m.ceil(invphi2 * (c-a))
            fb = f(b)


def ternary_search_float(f, left, right, rel_tol=1e-09, abs_tol=0.0):
    """
    Ternary search for the maximum point of f()

    df/dx must be always positive to the left of some point, and always negative to the right

    Note: If the return may be close to 0, set abs_tol to avoid excessive/infinite iteration

    >>> f = lambda x: -(x-3.5)**2
    >>> _ = ternary_search_float(f, 0, 10)
    >>> round(_, 6)
    3.5
    """
    assert left <= right

    invphi2 = (3-m.sqrt(5)) / 2

    a, d = left, right
    b = a + invphi2 * (d-a)
    c = b + invphi2 * (d-b)
    fb = f(b)
    fc = f(c)

    while not m.isclose(a, d, rel_tol=rel_tol, abs_tol=abs_tol):
        if fb < fc:
            a = b
            b, fb = c, fc
            c = b + invphi2 * (d-b)
            fc = f(c)
        else:
            d = c
            c, fc = b, fb
            b = c - invphi2 * (c-a)
            fb = f(b)

    return c


# if __name__ == "__main__":
if False:  # pylint: disable= using-constant-test
    import doctest
    doctest.testmod()

#endregion logsearch.py
#endregion bcf
###############################################################################

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

def ceildiv(a, b):
    q, r = divmod(a, b)
    return q + bool(r)

def impossible(x):
    cost = sum(ceildiv(a, x)-1 for a in A)
    return cost > K

print(binary_search_int(impossible, 1, int(1e9)))

Submission status: Accepted

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

num = n + k
count = 0
s = 0
l = max(a)
while True:
    count = 0
    mid = (s + l) / 2
    for i in range(n):
        if a[i] % mid == 0:
            count += a[i] // mid
        else:
            count += a[i] // mid + 1
    if count > num:
        s = mid
    else:
        l = mid
    temp = (s + l) / 2
    if abs(mid - temp) < 0.001:
        break
if mid == int(mid):
    print(int(mid))
else:
    print(int(mid) + 1)

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

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

def ceil(a,b):
    return a//b + int(a%b != 0)

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

ok = max(A)
ng = 0

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

print(ok)

Submission status: Accepted

Solution code:

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

ub = 10 ** 9 + 7
lb = 0
while ub - lb > 1:
    mid = (ub + lb) // 2

    res = 0
    for v in X:
        res += (v - 1) // mid

    if res <= K:
        ub = mid
    else:
        lb = mid

if K == 0:
    print(max(X))
else:
    print(ub)

Submission status: Accepted

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


a.sort()

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

def solve(num):
    ret=0
    for tmp in a:
        ret+= tmp//num
        if tmp%num==0:
            ret-=1
    return k>=ret

l=0
r=10**18
while r-l>1:
    mid=(l+r)//2

    if solve(mid):
        r=mid
    else:
        l=mid

print(min(max(a),r))
#print(min(min(a),r))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def cut(N):
    if N % r == 0:
        return N // r - 1
    else:
        return N // r
def solve(l):
    global r
    r = l
    b = list(map(cut, a))
    if sum(b) > k:
        return False
    else:
        return True
n, k = map(int, input().split())
a = list(map(int, input().split()))
u = max(a)
s = 0
while s + 1 < u:
    if solve((u + s) // 2):
        u = (u + s) // 2
    else:
        s = (u + s) // 2
print(u)

Submission status: Accepted

Solution code:
import math
def is_ok(mid,K,A):
    p = 0
    for i in A:
        p += (i - 1)// mid
    if p > K:
        return False
    else:
        return True
N,K = map(int,input().rstrip().split(" "))
A = list(map(int,input().rstrip().split(" ")))
A.sort()
maxi = A[0]

ng = 0
ok = 10 ** 9
while(abs(ng - ok) > 1):
    mid = (ok + ng) // 2
    if is_ok(mid,K,A):
        ok = mid
    else:
        ng = mid
print(ok)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
A=list(map(int,input().split()))
high=max(A)
low=0
while high-low>1:
    cnt=0
    now=(low+high)//2
    for a in A:
        cnt+=max((a-1)//now,0)
        if cnt>k:
            break
    if cnt>k:
        low=now
    else:
        high=now
    #print(cnt,low,high)
print(high)