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:
n,k=map(int,input().split())

A=[int(i) for i in input().split()]
CP=A[:]
R=[0 for i in range(n)]

suma=sum(A)
cnt=0
for i in range(n):
    zak=A[i]*k//suma
    R[i]=zak
    cnt+=zak
    A[i]=A[i]/(zak+1)

A=[(-CP[i]/(R[i]+1),CP[i],R[i]) for i in range(n)]

import heapq
import math

heapq.heapify(A)
for i in range(k-cnt):
    now=heapq.heappop(A)
    newr=now[2]+1
    newz=now[1]/(newr+1)
    heapq.heappush(A,(-newz,now[1],newr))

print(math.ceil(-heapq.heappop(A)[0]))

Submission status: Accepted

Solution code:
import sys
import numpy as np

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

def main(A, K):
    l, r = 0, 1 << 30

    def test(x):
        return np.sum((A + x - 1) // x - 1) <= K

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

N, K = map(int, readline().split())
A = np.array(read().split(), np.int64)

print(main(A, K))

Submission status: Accepted

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

left = 0
right = 10**10


for _ in range(100):
    mid = left + (right - left) / 2
    count = 0
    for i in range(n):
        count += (a[i]-1)//mid

    if count > k:
        left = mid
    else:
        right = mid

print(ceil(right))

Submission status: Accepted

Solution code:
def solve(a): #長さaにするのに何回いるか
  ret = 0
  for x in A:
    if x%a == 0:
      temp = x//a-1
    else:
      temp = x//a
    ret += temp
  return ret

N,K = map(int,input().split())
A = list(map(int,input().split()))
total = N+K
Sum = sum(A)
MAX = pow(10,9)+10
ng = 0
ok = MAX
while abs(ok-ng) > 1:
  mid = (ok+ng)//2
  if solve(mid) <= K:
    ok = mid
  else:
    ng = mid
print(ok)
#print(solve(3))

Submission status: Accepted

Solution code:
import sys
from collections import deque
import bisect
import copy
import heapq
import itertools
import math
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 10 ** 9 + 7

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


def main():
    N, K = read_values()
    A = read_list()

    D = {}
    L = []

    l = 1
    r = max(A) + 1

    while l != r:
        m = (l + r) // 2 
        k = 0

        for a in A:
            k += (a - 1) // m 
        if k > K:
            l = m + 1
        else:
            r = m

    print(r)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
A=list(map(int,input().split()))
def f(L):
    res=0
    for x in A:
        res+=(x-1)//L
    return res
l=0
r=max(A)
while r-l>1:
    M=(r+l)//2
    if f(M)>K:
        l=M
    else:
        r=M
print(r)

Submission status: Accepted

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

ng = 0
ok = 1001001001

while ok - ng > 1:
    mid = (ng + ok) // 2
    count = 0
    for A in As:
        count += -((-A) // mid)
        count -= 1

    if count <= K:
        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 isable(n):
    tmp = 0
    for i in range(N):
        tmp += (A[i]-0.5)//n
    if K >= tmp:
        return True
    else:
        return False


left = 0
right = 10**9

while right-left != 1:
    if isable((right+left)//2):
        right=(right+left)//2
    else:
        left=(right+left)//2

print(right)

Submission status: Accepted

Solution code:
def hersCode(L):
  ok = 10 ** 9 + 1
  ng = 0
  while abs(ok - ng) > 1:
    mid = abs(ok + ng) // 2
    if nasu(L, mid):
      ok = mid
    else:
      ng = mid
  return ok

def nasu(L, n):
  cnt = 0
  for x in L:
    div, mod = divmod(x, n)
    cnt += div - 1
    if mod != 0:
      cnt += 1
  if cnt <= K:
    return True
  else:
    return False

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

ans = hersCode(A)

print(ans)

Submission status: Accepted

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

# [ok, ng) - Maximum
# (ng, ok] - Minimum
# ok が 最終的な答え
ok = max(A)
ng = 0
while abs(ok - ng) > 1:
    mid = (ok + ng) // 2

    cnt = 0
    for a in A:
        l = (a + mid - 1) // mid
        cnt += l - 1
    if cnt <= K:
        ok = mid
    else:
        ng = mid

print(ok)

Submission status: Accepted

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

def mp(): return map(int, input().split())
def lmp(): return list(map(int, input().split()))

n,k = mp()
a = lmp()
l = 0
r = int(1e9+5)
while r - l != 1:
    m = (l+r)//2
    cnt = 0
    for i in range(n):
        cnt += (a[i]-1) // m
    if cnt <= k:
        r = m
    else:
        l = m
print(r)

Submission status: Accepted

Solution code:
from math import ceil

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


def check(l):
    cnt = sum(ceil(a / l) - 1 for a in A)
    return cnt <= K

lb, ub = 0, max(A)
for _ in range(50):
    mid = (lb + ub) / 2
    if check(mid):
        ub = mid
    else:
        lb = mid
print(ceil(ub))

Submission status: Accepted

Solution code:
mod = 1000000007
eps = 10**-9


def main():
    import sys
    input = sys.stdin.readline

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

    ok = max(A)
    ng = 0
    mid = (ok+ng) // 2
    while ok - ng > 1:
        cnt = 0
        for a in A:
            cnt += ((a-1) // mid)
        if cnt <= K:
            ok = mid
        else:
            ng = mid
        mid = (ok+ng)//2
    print(ok)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import heapq

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

b = []
ssum = 0
for item in a:
    kosu = (k * item // a_sum) + 1
    dv = item / kosu
    b.append((-dv, kosu, item))
    ssum += (kosu - 1)

left = k - ssum
heapq.heapify(b)

while left > 0:
    left -= 1
    _, kosu, item = heapq.heappop(b)
    if item / (kosu + 1) <= 1:
        print('1')
        exit()
    else:
        heapq.heappush(b, (-(item / (kosu + 1)), kosu+1, item))

_, kosu, item = heapq.heappop(b)
print((item + kosu - 1) // kosu)

Submission status: Accepted

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

x=0
y=max(A)

def f(l):
  nums=0
  for a in A:
    if a%l==0:
      nums+=a//l-1
    else:
      nums+=a//l
  if nums>K:
    return False
  else:
    return True

while y-x>1:
  tmp=(x+y)//2
  if f(tmp)==True:
    y=tmp
  else:
    x=tmp
    
print(y)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def exit(*argv, **kwarg):
    print(*argv, **kwarg)
    sys.exit()


def mina(*argv, sub=1): return list(map(lambda x: x - sub, argv))
# 受け渡されたすべての要素からsubだけ引く.リストを*をつけて展開しておくこと


def a_int(): return int(read())


def ints(): return list(map(int, read().split()))


def read_col(H):
    '''H is number of rows
    A列、B列が与えられるようなとき
    ex1)A,B=read_col(H)    ex2) A,=read_col(H) #一列の場合'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return tuple(map(list, zip(*ret)))


def read_tuple(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


def read_matrix(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return ret
    # return [list(map(int, read().split())) for _ in range(H)] # 内包表記はpypyでは遅いため


MOD = 10**9 + 7
INF = 2**31  # 2147483648 > 10**9
# default import
from collections import defaultdict, Counter, deque
from operator import itemgetter, xor, add
from itertools import product, permutations, combinations
from bisect import bisect_left, bisect_right  # , insort_left, insort_right
from functools import reduce
from math import gcd


def lcm(a, b):
    # 最小公倍数
    g = gcd(a, b)
    return a // g * b


# 答えをxと仮定
# x以上で切れる最小が答え
N, K = ints()
A = ints()


def is_ok(arg):
    # x以上で切れる場合にTrueを返す
    cnt = 0
    for a in A:
        cnt += a // arg
        if a % arg == 0:  # ぴったり切れるとき
            cnt -= 1
    return cnt <= K  # xでは切れる


def meguru_bisect(ng, ok):
    '''
    define is_okと
    初期値のng,okを受け取り,is_okを満たす最小(最大)の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, 10**9 + 1))

Submission status: Accepted

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

if sum(A) <= N+K:
  print(1)
  sys.exit()

lt = 1
rt = 10**9

def det(x):
  if sum([math.ceil(A[i]/x) for i in range(N)]) <= N+K:
    return True
  else:
    return False
  
while rt - lt > 1:
  ct = (lt + rt) // 2
  if det(ct):
    rt = ct
  else:
    lt = ct
  
  
print(rt)

Submission status: Accepted

Solution code:
n,k = list(map(int,input().split()))
arr = list(map(int,input().split()))
lo = 1
hi = 10**12
ans = max(arr)
while lo<=hi:
    t = 0
    m = (hi+lo)//2
    for i in range(n):
        if arr[i]>m:
            req = arr[i]//m
        else:
            req=  0
        t+=req
    if t<=k:
        ans = m
        hi = m-1
    else:
        lo = m+1
print(ans)

Submission status: Accepted

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

from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
from collections import deque, defaultdict, Counter
from itertools import combinations, permutations, combinations_with_replacement
from itertools import accumulate
from math import ceil, sqrt, pi, radians, sin, cos

MOD = 10 ** 9 + 7
INF = 10 ** 18

#N = int(input())
N, K = map(int, input().split())
A = list(map(int, input().split()))
#A = [int(input()) for _ in range(N)]
#ABC = [list(map(int, input().split())) for _ in range(N)]
#S = input()
#S = [input() for _ in range(N)]

max_a = max(A)

ok = max_a
ng = 0

while ok - ng != 1:
    mid = (ok + ng) // 2
    cnt = 0
    for a in A:
        cnt += a // mid
        if a % mid == 0:
            cnt -= 1
    if cnt <= K:
        ok = mid
    else:
        ng = mid

print(ok)

Submission status: Accepted

Solution code:
import bisect
import copy
import heapq
import math
import sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
sys.setrecursionlimit(500000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

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

l,h=0,max(a)
while h-l>1:
    mid=(h+l)//2
    # print(l,h,mid)
    cnt=0
    for i in range(n):
        cnt+=math.ceil(a[i]/mid)-1
    #     print(a[i]/mid)
    # print(cnt)
    if cnt<=k:
        h=mid
    else:
        l=mid

# print(l)
print(h)

Submission status: Accepted

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

def check(k):
    cnt = 0
    for a in A:
        cnt += math.ceil(a/k) - 1
    return cnt <= K

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

print(r)

Submission status: Accepted

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


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

#bottom:ng, top:ok
bottom, top = 0, max(a)

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

print(top)

Submission status: Accepted

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


l = 0
r = 10 ** 9 + 1

while r - l > 1:
    m = (r + l) // 2
    cnt = 0
    for i in A:
        cnt += i // m
        if i >= m and i % m == 0:
            cnt -= 1
    if cnt <= K:
        r = m
    else:
        l = m

print(r)

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
A=list(map(int,input().split()))
A=[10*A[i] for i in range(N)]

def cond(n):
    cnt=0
    for i in range(N):
        q=(A[i]-1)//n
        cnt+=q

    return cnt<=K

start=0
end=10**10
while end-start>1:
    test=(end+start)//2
    if cond(test):
        end=test
    else:
        start=test

ans=end//10
if end%10>0:
    ans+=1

print(ans)

Submission status: Accepted

Solution code:
import sys
import numpy as np
import math
read = sys.stdin.read
readline = sys.stdin.buffer.readline

sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7


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

    low = 0
    high = 10**10
    while high-low>0.000001:
        mid = (high+low)/2
        k = np.sum(np.ceil(A/mid-1))
        if k>K:
            low = mid
        else:
            high = mid
    print(math.ceil(low))


if __name__ == '__main__':
    main()

Submission status: Accepted

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

#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode()

def main():
	n,k=MI()
	A=LI()


	l=1
	r=max(A)+10

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

		for i in A:
			cnt+=(i-1)//(m-1)
		#print(l,m,r,cnt)
		if cnt<=k:
			r=m
		else:
			l=m



	print(l)
















if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
# coding: utf-8
# hello worldと表示する
#float型を許すな
#numpyはpythonで
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7
n,k=MI()
lis=LI()
left=0
right=10**9+10
while left+1<right:
    x=(left+right)//2
    count=0
    for i in range(n):
        count+=-(-lis[i]//x)-1
    #print(count)
    if count<=k:
        right=x
    else:
        left=x
print(right)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
l=0
r=max(a)+1
while r-l>1:
	cnt=0
	mid=(l+r+1)//2
	if mid==0:
		print(1)
		exit()
	for x in a:
		if x>1:
			cnt+=(x-1)//mid
	if cnt<=k:
		r=mid
	else:
		l=mid
print(r)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10**7)
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり
def LI2(): return list(map(int,sys.stdin.readline().rstrip()))  #空白なし
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())  #空白あり
def LS2(): return list(sys.stdin.readline().rstrip())  #空白なし

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)

Submission status: Accepted

Solution code:
import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 19
MOD = 10 ** 9 + 7
EPS = 10 ** -10

def bisearch_min(mn, mx, func):
    ok = mx
    ng = mn
    while ng+1 < ok:
        mid = (ok+ng) // 2
        if func(mid):
            ok = mid
        else:
            ng = mid
    return ok

def check(m):
    cnt = 0
    for a in A:
        cnt += ceil(a, m) - 1
    return cnt <= K

N, K = MAP()
A = LIST()

res = bisearch_min(0, INF, check)
print(res)

Submission status: Accepted

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

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


ok = 10**10
ng = 0

while ok-ng > 1:
    m = (ok+ng)//2
    c = 0
    for e in a:
        if e%m == 0:
            c += e//m - 1
        else:
            c += e//m

    if c <= k:
        ok = m
    else:
        ng = m
print(ok)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict, deque, Counter
import math

# import copy
from bisect import bisect_left, bisect_right
# import heapq

sys.setrecursionlimit(1000000)

# input aliases
input = sys.stdin.readline

getS = lambda: input().strip()
getN = lambda: int(input())
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]

INF = 10 ** 20
MOD = 10**9 + 7
divide = lambda x: pow(x, MOD-2, MOD)


def nck(n, k, kaijyo):
    return (npk(n, k, kaijyo) * divide(kaijyo[k])) % MOD


def npk(n, k, kaijyo):
    if k == 0 or k == n:
        return n % MOD
    return (kaijyo[n] * divide(kaijyo[n-k])) % MOD


def kaijyo(n):
    ret = [1]
    for i in range(1, n + 1):
        ret.append((ret[-1] * i)% MOD)
    return ret

def judge(anums, k, mid):
    if mid == 0:
        return False
    tmp = 0
    for anum in anums:
        tt = anum // mid
        if mid * tt != anum:
            tt += 1
        tmp += tt - 1

    if tmp <= k:
        return True
    else:
        return False

def solve():
    n, k = getList()
    anums = getList()

    mn = 0
    mx = sum(anums) + 1
    while(mx - mn > 1):
        mid = (mn + mx) // 2
        if judge(anums, k, mid):
            mx = mid
        else:
            mn = mid

    if judge(anums, k, mn):
        print(mn)
    else:
        print(mx)


def main():
    n = getN()
    for _ in range(n):
        solve()


if __name__ == "__main__":
    # main()
    solve()

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
from math import ceil, floor
N, K = map(int, input().split())
A = [int(i) for i in input().split()]

ng, ok = 0, 10 ** 9
for _ in range(50) :
  mid = (ng + ok) / 2
  ret = 0
  for a in A :
    ret += floor(a / mid)
  if ret <= K :
    ok = mid
  else :
    ng = mid
    
print(ceil(ng))

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
A=list(map(int,input().split()))
l,r=1,10**9+1
while r-l>1:
    t=(l+r)//2
    k=sum([(a+t-2)//(t-1)-1 for a in A])
    if K<k:
        l=t
    else:
        r=t
print(l)

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush
from bisect import bisect_left,bisect_right 
import sys,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))


n,k = inpl()
a = inpl()
ok = max(a)
ng = 0
def sol(x):
    cnt = 0
    for i in range(n):
        cnt += (a[i]+x-1)//x-1
    if cnt <= k:
        return True
    return False
while abs(ok-ng) > 1:
    mid = (ok+ng)//2
    if sol(mid):
        ok = mid
    else:
        ng = mid
print(ok)

Submission status: Accepted

Solution code:
# 2020年6月17日

# 修行という概念がない場合、消化コストを大から小に並べて食べにくさを小から大に並べて順にマッチングさせれば良い。
# そうでない状態から2つを交換したときに最大値が下がる方向にしか行かないため。

# 修行をするなら最大値を引き下げるところに修行をするのが最適なので、
# 無修行状態の結果を優先度付きキューに入れる→K回最大値を取り出してコストを引いて再投入→を繰り返す。
# 本当か? やってるうちに最適な組み合わせが変わらないか? →変わらない。食べにくさを昇順に並べたときに消化コストが降順になるのが最善手なので。
# あとKが大きいのでこれだと間に合わない。

# 決め打ち二分探索か?
# あ、それだわ。

# Python TLE 2秒以上
# PyPy 287ms

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

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


def is_valid(unit):
    # k回以下の切断で実現可能か

    n_cut = sum(map(lambda p: (p+unit-1) // unit - 1, lengths))
    # print(unit, n_cut)
    
    return n_cut <= k


unit_ok = 10 ** 9 + 1
unit_ng = 0

# めぐる式二分探索
while abs(unit_ok - unit_ng) > 1:
    mid = (unit_ok + unit_ng) // 2
    if is_valid(mid):
        unit_ok = mid
    else:
        unit_ng = mid

print(unit_ok)

Submission status: Accepted

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

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

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


left = 0 # False
right = 10**10 # True
while left + 1 < right:
    mid = (left + right) // 2
    if check(mid):
        right = mid
    else:
        left = mid

print(right)

Submission status: Accepted

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

l = 0
r = 10**10

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

Submission status: Accepted

Solution code:
def main():
    from math import ceil

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

    def binary_search(*, ok, ng, func):
        for _ in range(60):
            mid = (ok + ng) / 2
            if func(mid):
                ok = mid
            else:
                ng = mid
        return ok

    def is_ok(mid):
        cnt = 0
        for x in A:
            q, r = divmod(x, mid)
            cnt += q
            if r == 0:
                cnt -= 1
        return cnt <= K

    ma = max(A)
    res = binary_search(ok=ma, ng=0, func=is_ok)

    print(ceil(res))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    L, R = 0, max(a)
    while L+1 < R:
        P = (L+R+1)//2
        tmp = 0
        for v in a:
            if P < v:
                if v % P == 0:
                    tmp += v//P - 1
                else:
                    tmp += v//P
        if tmp <= k:
            R = P
        else:
            L = P
    print(R)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def check(A, K, t):
    # K回で長さt以下にできるか？（t：整数）
    cnt = 0
    for a in A:
        cnt += (a - 1) // t
    return cnt <= K


def main():
    N, K = list(map(int, input().split()))
    A = list(map(int, input().split()))
    ng, ok = 0, max(A)
    while ok - ng > 1:
        mid = (ok + ng) // 2
        if check(A, K, mid):
            ok = mid
        else:
            ng = mid
    print(ok)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
A = list(map(int,input().split()))
S = sum(A)
k = 0
B = []
for i in range(N):
    l = int(K*A[i]/S)
    k += l
    B.append([A[i]/(l+1),l+1])
L = K-k
B.sort(reverse = True)
if L == 0:
    if B[0][0].is_integer():
        print(int(B[0][0]))
    else:
        print(int(B[0][0])+1)
else:
    M = B[0][0]*B[0][1]/(B[0][1]+1)
    for i in range(1,L):
        b= B[i][0]*B[i][1]/(B[i][1]+1)
        if b > M:
            M = b
    if M < B[L][0]:
        M = B[L][0]
    if M.is_integer():
        print(int(M))
    else:
        print(int(M)+1)

Submission status: Accepted

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

left = 0 # できない
right = a[0] # できる
while left+1 < right:
    mid = (left+right) // 2
    cnt = 0
    for i in range(n):
        if a[i]%mid == 0:
            cnt += a[i] // mid - 1
        else:
            cnt += a[i] // mid
        if cnt > k: break
    if cnt > k:
        left = mid
    else:
        right = mid
print(right)

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
import math
sys.setrecursionlimit(10**8)
stdin = sys.stdin


def ni(): return int(ns())


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


def naa(N): return [na() for _ in range(N)]


def ns(): return stdin.readline().rstrip()  # ignore trailing spaces


N, K = na()
A_array = na()

min_length = 0
max_length = 2 * 10 ** 9

while(max_length - min_length > 0.01):
    mid = (min_length + max_length) / 2
    cut_cnt = 0
    for a in A_array:
        c = a // mid
        if a - mid * c > 0:
            c += 1
        cut_cnt += (c - 1)
    # print(mid, cut_cnt)
    if cut_cnt <= K:
        max_length = mid
    else:
        min_length = mid

# print(max_length)


ans1 = math.floor(max_length)
ans2 = math.ceil(max_length)

if ans1 == 0:
    print(1)
    exit()

cut_cnt = 0
for a in A_array:
    c = a // ans1
    if a - ans1 * c > 0:
        c += 1
    cut_cnt += (c - 1)

if cut_cnt <= K:
    print(ans1)
else:
    print(ans2)

Submission status: Accepted

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

# にぶたん: 答えをx以下にできるか？
ok, ng = 10 ** 9 + 1, 0
while abs(ok - ng) > 1:
    x = (ok + ng) // 2
    cnt = 0

    for a in A:
        if a <= x:
            continue

        cnt += a // x
        if cnt > K:
            ng = x
            break
    else:
        ok = x

print(ok)

Submission status: Accepted

Solution code:
#Binary Search:
N, K = map(int,input().split())
A = list(map(int,input().split()))
s = 0
t = max(A)

while s + 1 < t:
  m = (s + t) // 2
  temp = 0
  for i in A:
    temp += (i - 1) // m 
  if temp <= K: # feasible
    t = m
  else: # infeasible
    s = m
print(t)

Submission status: Accepted

Solution code:
#from collections import deque,defaultdict
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 10**18
R = 10**9 + 7
#R = 998244353

def ddprint(x):
  if DBG:
    print(x)

def foo(x):
    cnt = 0
    for i in range(n):
        cnt += (a[i]-1)//x
    return k>=cnt

n,k = inm()
a = inl()
mn = 0
mx = max(a)
while mn+1<mx:
    mid = (mn+mx)//2
    if foo(mid):
        mx = mid
    else:
        mn = mid
print(mx)

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    n, k = map(int, readline().split())
    a = list(map(int, readline().split()))

    ok = max(a)
    ng = 0

    while abs(ng - ok) > 1:
        mid = (ok + ng) // 2
        cnt = 0
        for x in a:
            cnt += (x + mid - 1) // mid - 1
        if cnt <= k:
            ok = mid
        else:
            ng = mid

    print(ok)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

def cal( max_length ):
    cut_count = 0 
    for l in logs :
        cut_count += (l//max_length -1)
        if l % max_length != 0 :
            cut_count += 1
    return cut_count <= K 

i = 1 
j = max(logs)
while i < j :
    m = (i+j)//2
    if cal(m) :
        j = m
    else :
        i = m+1

print(i)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
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 LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def cnt(m):
    res=0
    for a in aa:res+=(a+m-1)//m-1
    return res

n,k=MI()
aa=LI()
l=0
r=max(aa)
while l+1<r:
    m=(l+r)//2
    if cnt(m)>k:l=m
    else:r=m
print(r)

Submission status: Accepted

Solution code:

import sys
sys.setrecursionlimit(10**7)

readline = sys.stdin.buffer.readline
def readstr():return readline().rstrip().decode()
def readstrs():return list(readline().decode().split())
def readint():return int(readline())
def readints():return list(map(int,readline().split()))
def printrows(x):print('\n'.join(map(str,x)))
def printline(x):print(' '.join(map(str,x)))


n,k = readints()
a = readints()

l = 0
r = 10**10

while r-l>1:
    m = (l+r)//2
    x = [(a[i]-1)//m for i in range(n)]
    if sum(x)<=k:
        r = m
    else:
        l = m

print(r)

Submission status: Accepted

Solution code:
import math
import sys
from itertools import permutations
input = sys.stdin.readline

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

fin = 1000000000000
def check(x):
	global arr, n, k, fin
	# print("x",x)
	cur=0
	for i in range(n):
		cur+=(math.ceil(arr[i]/x)-1)
		# print(cur)
		if cur>k:
			return False
	
	return True

def bs(l, r):
	global arr, n, k, fin
	if r>=l:
		mid = l+(r-l)//2
		if check(mid):
			fin = min(fin, mid)
			bs(l, mid-1)
		else:
			bs(mid+1, r)

if k==0:
	print(max(arr))
else:
	bs(1, max(arr))
	print(fin)