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
# 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 - (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 sys
import re
import math
import collections
import bisect
import itertools
import fractions
import functools
import copy
import heapq
import decimal
import statistics
import queue

# import numpy as np

sys.setrecursionlimit(10 ** 9)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))
na1 = lambda: list(map(lambda x: int(x) - 1, sys.stdin.readline().split()))


# ===CODE===


def main():
    n, k = ns()
    a = na()
    a.sort(reverse=True)
    upper = 10**9 + 1
    under = 0

    while upper - under > 1:
        middle = (upper + under) // 2

        tk = k
        flg = True
        for ai in a:
            if ai <= middle:
                break

            ta = ai
            tk -= int(ta // middle)
            if tk < 0:
                flg = False
                break

        if flg:
            upper = middle
        else:
            under = middle

    if k == 0:
        print(max(a))
    else:
        print(math.ceil((upper + under) / 2))

if __name__ == '__main__':
    main()

Submission status: Accepted

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

mi = 0
ma = 10**9
while(ma - mi != 1):
    c = 0
    mid = (ma + mi) // 2
    for i in range(N):
        c += A[i] // mid - (A[i] % mid == 0)
    if c > K:
        mi = mid
    else:
        ma = mid
print(ma)

Submission status: Accepted

Solution code:
from math import ceil
n, k, *A = map(int, open(0).read().split())
t = sum(A) / (n+k)
A = [a for a in A if int(a/t) >= 1]
X = []
for a in A:
    X.append(ceil(a / ceil(a/t)))
    X.append(ceil(a / int(a/t)))
X.sort()
print(X[sum(int(a/t)-1 for a in A) -k-1])

Submission status: Accepted

Solution code:
from heapq import heapify,heappop,heappush
from math import ceil

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
from math import ceil

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

    if cutable(A,N,K,1):
        return 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 math import *
import fractions
import collections
import itertools
import pprint
from collections import deque
from heapq import *
N,K=map(int,input().split())
A=list(map(int,input().split()))
maxnum=10**9+20
minnum=1
def is_ok(arg):
    return arg<=K
def mgr_bisect(ng,ok):
    while (abs(ok-ng)>1):
        mid=(ok+ng)//2
        cnt=0
        for i in range(N):
            cnt=cnt+ceil(A[i]/mid)-1
        if is_ok(cnt):
            ok=mid
        else:
            ng=mid
    return ok
print(mgr_bisect(0,10**9+1))

Submission status: Accepted

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

l=0
r=1e9+5

while l+1!=r:
    m = (l+r)//2
    cnt = 0
    for x in a:
        cnt += (x-1)//m
    if cnt <= k:
        r = m
    else:
        l = m
print(int(r))

Submission status: Accepted

Solution code:
import math
n,k=map(int,input().split())
a=list(map(int,input().split()))
ng=0
ok=10**9
while ok-ng >1:
  l = (ng+ok)//2
  kt=0
  for i in range(n):
    kt += a[i]//l - (0 if a[i]%l else 1)
  if kt <= k:
    ok = l
  else:
    ng = l
print(ok)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline


def solve():
    N, K = map(int, rl().split())
    A = list(map(int, rl().split()))
    
    def check(t):
        cnt = 0
        for ai in A:
            cnt += -(-ai // t) - 1
        return cnt <= K
    
    ok, ng = 10 ** 9, 0
    while 1 < ok - ng:
        mid = (ok + ng) // 2
        if check(mid):
            ok = mid
        else:
            ng = mid
    print(ok)


if __name__ == '__main__':
    solve()

Submission status: Accepted

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

left = 0
right = max(a)

while right - left > 1:
    mid = (right + left) // 2
    tmp = 0
    for i in a:
        tmp += (i - 1) // mid
    
    if tmp <= k:
        right = mid
    else:
        left = mid
        
print(right)

Submission status: Accepted

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

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

suki = 1000000000
kirai = 0
while suki-kirai>1:
	targ = (suki+kirai)//2
	cnt = 0
	mode = 1
	for i in range(n):
		cnt += -(-a[i]//targ)-1
		if cnt > k:
			mode = 0
			break
	if mode:
		suki = targ
	else:
		kirai = targ

print(math.ceil(suki))

Submission status: Accepted

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

Submission status: Accepted

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

def f(x):
    return sum((a+x-1)//x - 1 for a in A)

l = 0
r = 10**9+1 
while r - l > 1:
    mid = (l + r) // 2
    if f(mid) <= K:
        r = mid
    else:
        l = mid
print(r)

Submission status: Accepted

Solution code:
#import sys
#import numpy as np
import math
#from fractions import Fraction
import itertools
from collections import deque
from collections import Counter
import heapq
from fractions  import gcd
#input=sys.stdin.readline
#import bisect
n,k=map(int,input().split())
a=list(map(int,input().split()))
l=0
r=10**9
while r>l+1:
    mid=(l+r)//2
    res=0
    for i in range(n):
        res+=(math.ceil(a[i]/mid)-1)
    if res<=k:
        r=mid
    else:
        l=mid
print(r)

Submission status: Accepted

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

l, r = sum(A)//(N+K), A[-1]
if l == 0: l = 1

if sum([(a-1)//l for a in A]) <= K:
    print(l)
    exit()

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

    cuts = sum([(a-1)//m for a in A])

    if cuts <= K:
        r = m
    else:
        l = m

print(r)

Submission status: Accepted

Solution code:
n,k=map(int, input().split())
*a,=map(int, input().split())
mx=max(a)
mn=10**(-9)
from math import ceil
while mx-mn>10**(-5):
    md=(mx+mn)/2
    cnt=0
    for ai in a:
        cnt+=ceil(ai/md)-1
    if cnt<=k:
        mx=md
    else:
        mn=md
print(ceil(mn))

Submission status: Accepted

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

leq,high = 0,1e10
while high-leq > 1:
  l = int((leq+high)/2)
  cnt = 0
  for ai in a:
    cnt += int((ai-1)/l)
  if cnt>k:
    leq = l
  else:
    high = l

print(high)

Submission status: Accepted

Solution code:
n,k,*a=map(int,open(0).read().split())
l,r=0,10**9
while r-l>1:
  m=l+r>>1
  if sum(0--i//m for i in a)>n+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()))
A.sort()
M = max(A)
l,r = 1,M
cnt = 0
while l<=r:
    cnt = 0
    mid = (l+r)//2
    for a in A:
        tmp= a//mid if a>mid else 0
        cnt += tmp
    if cnt <=k:
        r = mid-1
    else:
        l = mid+1
print(l)

Submission status: Accepted

Solution code:
import sys
INF = 1 << 60
MOD = 10**9 + 7 # 998244353
sys.setrecursionlimit(2147483647)
input = lambda:sys.stdin.readline().rstrip()
def resolve():
    n, k = map(int, input().split())
    A = list(map(int, input().split()))

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

    l = 0
    r = 10 ** 10
    while r - l > 1:
        m = (l + r) // 2
        if check(m):
            r = m
        else:
            l = m
    print(r)
resolve()

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
l = list(map(int, input().split()))
lo, hi = 1, 9999999999999999
while lo < hi:
    mid = (lo + hi) // 2
    cnt = 0
    for i in range(n):
        if l[i] % mid == 0: cnt += (l[i] // mid) - 1
        else: cnt += (l[i] // mid)
    if cnt <= k: 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 check(x):
    res = 0
    for i in range(n):
        res +=  (a[i]-1) // x
    if res <= k:
        return True
    else:
        return False
r = 1000000000
if check(1):
    print(1)
    exit()
else:
    l = 1
    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,*a=map(int,open(0).read().split())
l,r=0,10**9
while r-l>1:
  m=l+r>>1
  if sum(0--i//m for i in a)<=n+k: r=m
  else: l=m
print(r)

Submission status: Accepted

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

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

suki = 1000000000
kirai = 0
while int(suki) != int(kirai):
	targ = (suki+kirai)/2
	cnt = 0
	mode = 1
	for i in range(n):
		cnt += (a[i]-1)//targ
		if cnt > k:
			mode = 0
			break
	if mode:
		suki = targ
	else:
		kirai = targ

print(math.ceil(suki))

Submission status: Accepted

Solution code:
import math 
N,K=map(int,input().split())
A=[int(x) for x in input().split()]
A=sorted(A)
left=0
right=max(A)
mid=max((left+right)//2,1)

while(right-left>=1):
    numofcut=0
    
    for i in range(N):
        numofcut+=math.ceil(A[i]/mid)-1
    #print(numofcut)
    if numofcut>K:
        left=mid+1
    else:
        right=mid
    mid=max((left+right)//2,1)
    if mid==1:
        break
print(mid)

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)//m
        
    if count > k:
        l = m
    else:
        r = m
    
print(r)

Submission status: Accepted

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

#めぐる式二分探索
def is_ok(i):
    su = 0
    for a in A:
        su += math.ceil(a / i) - 1
    if su <= 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

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

Submission status: Accepted

Solution code:
import math 
N,K=map(int,input().split())
A=[int(x) for x in input().split()]
A=sorted(A)
left=0
right=max(A)
mid=max((left+right)//2,1)

while(right-left>=1):
    numofcut=0
    
    for i in range(N):
        if A[i]%mid==0:
            numofcut+=(A[i]//mid) -1
        else:
            numofcut+=A[i]//mid
    #print(numofcut)
    if numofcut>K:
        left=mid+1
    else:
        right=mid
    mid=max((left+right)//2,1)
    if mid==1:
        break
print(mid)

Submission status: Accepted

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

#めぐる式二分探索
def is_ok(i):
    su = 0
    for a in A:
        su += (a-1) // i
    if su <= 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

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

Submission status: Accepted

Solution code:
f=lambda:[*map(int,input().split())]
n,k=f()
a=f()
def ok(x):
  c=0
  for i in a:
    c+=0--i//x
  return c<=n+k
l,r=0,10**9
while r-l>1:
  m=l+r>>1
  if ok(m): r=m
  else: l=m
print(r)

Submission status: Accepted

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

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

# search smallest i such that f(i) == True
def auto_bisearch_smallest(f, s = None):
	if s == None:
		s = 0
		w = -1
		while f(s) == True:
			s = w
			w *= 2
	e = s
	w = 1
	while f(e) == False:
		e = s + w
		w *= 2
	
	return bisearch_smallest(f, s, e + 1)

# search smallest i ( s <= i < e ) such that f(i) == True
def bisearch_smallest(f, s, e = None):
	if e == None:
		e = s - 1
		s = 0
	else:
		e -= 1
	
	while s < e:
		m = (s + e) // 2
		if f(m):
			e = m
		else:
			s = m + 1
	
	if s == e and f(s):
		return s
	else:
		return -1

def calc(length):
	count = 0
	for a in A_list:
		if a > length:
			if a % length == 0:
				count += (a // length) - 1
			else:
				count += a // length
	return count

print(auto_bisearch_smallest(lambda length: calc(length) <= K, 1))

Submission status: Accepted

Solution code:
#揃える長さを決め打って二分探索
import sys
import math
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0
n,k = map(int,readline().split())
lst1 = list(map(int,readline().split()))
lst1.sort(reverse=True)
def func(mid): #ここが関数部分
    res = 0
    for i in range(n):
        if mid >= lst1[i]:
            continue
        res += math.ceil(lst1[i]/mid)-1
        if res > k:
            return False
    return True


def binary_search(): #2分探索
    ok = 10**9
    ng = 0
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if func(mid):
            ok = mid
        else:
            ng = mid

    return ok

print(binary_search())

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
    for i in range(100):
        # while right - left > 1.0e-6:
        mid = (right + left) / 2
        count = 0
        for a in A:
            count += int(math.ceil(a / mid))-1
        if count <= K:
            right = mid
        else:
            left = mid
    print(int(math.ceil(left)))

    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from math import floor

m=0
M=10**9+1

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

def OK(p):
    if sum([(a-1)//p for a in A])<=K:
        return True
    else:
        return False

while M-m>1:
    p=(m+M)//2
    if OK(p):
        M=p
    else:
        m=p
print(M)

Submission status: Accepted

Solution code:
import heapq
import math
import sys

input = sys.stdin.readline


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

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

    l, r = 0, max(A)
    while r - l > 1:
        mid = (l+r)//2
        if C(mid) <= K:
            r = mid
        else:
            l = mid
    
    print(r)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import math

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

def check(L):
    return sum(math.ceil(a / L)-1 for a in A) <= K

answer=max(A)
lo = 1
hi = answer+1
while lo < hi:
    m = (lo + hi)//2
    ok = check(m)
    if ok: 
        answer=min(m, answer)
        hi=m
    else:
        lo=m+1
print(answer)

Submission status: Accepted

Solution code:
import sys
from functools import lru_cache, cmp_to_key
from heapq import merge, heapify, heappop, heappush
from math import *
from collections import defaultdict as dd, deque, Counter as C
from itertools import combinations as comb, permutations as perm
from bisect import bisect_left as bl, bisect_right as br, bisect
from time import perf_counter
from fractions import Fraction
# import numpy as np


mod = int(pow(10, 9) + 7)
mod2 = 998244353
def data(): return sys.stdin.readline().strip()
def out(*var, end="\n"): sys.stdout.write(' '.join(map(str, var))+end)
def L(): return list(sp())
def sl(): return list(ssp())
def sp(): return map(int, data().split())
def ssp(): return map(str, data().split())
def l1d(n, val=0): return [val for i in range(n)]
def l2d(n, m, val=0): return [l1d(n, val) for j in range(m)]

try:
    # sys.setrecursionlimit(int(pow(10,6)))
    sys.stdin = open("input.txt", "r")
    sys.stdout = open("../output.txt", "w")
except:
    pass


# @lru_cache(None)




def pos(m):
    ans=0
    for ele in A:
        ans+=((ele-1)//m)
    return ans<=k

n,k=L()
A=L()
l=1
r=max(A)
ans=r
while(l<=r):
    m=(l+r)//2
    if pos(m):
        r=m-1
        ans=m
    else:
        l=m+1
print(ceil(ans))

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
ok=max(a)
ng=0
while ok-ng>1:
    mid=(ok+ng)//2
    cnt=0
    for i in range(n):
        num=a[i]
        cnt+=-(-num//mid)-1
    if cnt<=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()))
a.sort()

if k==0:
    print(a[-1])
    exit()


# めぐる式二部探索
l=0
r=pow(10,11)
while r-l>1:
    # rは常にOK、lは常にNG。
    mid=l+(r-l)//2
    cnt=k
    flag=True
    for i in range(n):
        if a[i]>mid:
            x=-(-a[i]//mid)-1
            cnt-=x

    # なんらかの判定
    if cnt>=0:
        r = mid  # 判定がOKのとき→範囲を左に狭める
    else:
        l = mid  # 判定がNGのとき→範囲を右に狭める

print(r)

Submission status: Accepted

Solution code:
from math import ceil
n, k, *A = map(int, open(0).read().split())
t = sum(A) / (n+k)
A = [a for a in A if int(a/t) >= 1]
c = k - sum(int(a/t)-1 for a in A)
X = []
for a in A:
    X.append(ceil(a / ceil(a/t)))
    X.append(ceil(a / int(a/t)))
X.sort()
print(X[-c-1])

Submission status: Accepted

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


low=0
high=10**9+1

while low<=high:
    mid=(low+high)//2
    if mid==0: #0-div errorを消す
        print(1)
        exit()

    cnt=0
    for a in A:
        v=ceil(a/mid)
        cnt+=v-1

    if cnt<=K:
        high=mid-1
    else:
        low=mid+1
print(low)

Submission status: Accepted

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

left = 0
right = max(A) + 1

while left+1!=right:
  mid = (left + right)//2
  x = 0
  for a in A:
    x += math.ceil(a/mid) - 1
  if x<=K:
    right = mid
  else:
    left = mid
  
print(right)

Submission status: Accepted

Solution code:
import math

def main():
    _, k = map(int, input().split())
    arr = list(map(int, input().split()))
    l, r = 1, 1000000000
    while l < r:
        m = (l + r) // 2
        cnt = 0
        for val in arr:
            cnt += math.ceil(val / m) - 1
        if cnt > k:
            l = m + 1
        else:
            r = m
    print(l)
  
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import heapq, math, sys

N, K = map(int, input().split())
A = sorted(list(map(int, input().split())), reverse=True)
maxA = A[0]
pre = -1
while len(A) != pre:
    if len(A) == 0:
        print(math.ceil(maxA))
        sys.exit()
    pre = len(A)
    meanA = math.ceil(sum(A)/(len(A)+K))
    for i, a in enumerate(A):
        if a <= meanA:
            A = A[:i]
            break


cuts = [0]*(i+1)
meanA = (sum(A)/(len(A)+K))
for i, a in enumerate(A):
    cut_at_least = (math.floor(a/meanA) - 1)
    cuts[i] = cut_at_least
    K -= cut_at_least
hq = [(-a/(cut+1), i) for i, (a, cut) in enumerate(zip(A, cuts))]
heapq.heapify(hq)
lenhq = len(hq)
for k in range(K):
    l, i = heapq.heappop(hq)
    cuts[i] += 1
    if k <= N:
        heapq.heappush(hq, (-A[i]/(cuts[i]+1), i))
l, i = heapq.heappop(hq)
print(math.ceil(-l))

Submission status: Accepted

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

def is_ok(arg):
  # 条件を満たすかどうか？問題ごとに定義
  # arg以下になるように各々の木をきる。回数を足し合わせて、K以下かどうか判定する
  cnt = 0
  for a in A:
    cnt += ceil(a / arg) - 1
  return cnt <= K

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

ng = 0
ok = 10**9 + 1

ans = meguru_bisect(ng,ok)
print(ceil(ans))

Submission status: Accepted

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

low = 1
high = max(A)

while low < high:
    mid = (low + high) // 2

    k = 0
    for a in A:
        v = a // mid
        if a % mid == 0:
            v -= 1
        k += v

    if k <= K:
        high = mid
    else:
        low = mid + 1

print(low)

Submission status: Accepted

Solution code:
import heapq as hq

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

cnt = [0]*n

a_sum = sum(a)
for i in range(n):
    cnt[i] = k*a[i]//a_sum

cnt_sum = sum(cnt)
r = k - cnt_sum
l = []

for i in range(n):
    hq.heappush(l, (-a[i]/(cnt[i]+1), i))

for _ in range(r):
    x,i = hq.heappop(l)
    cnt[i] += 1
    hq.heappush(l, (-a[i]/(cnt[i]+1), i))

x,i = hq.heappop(l)
print(int(x // 1 * -1))

Submission status: Accepted

Solution code:

n,k=map(int,input().split())
a=list(map(int,input().split()))
if k==0:
    print(max(a))
    exit()
a.sort()
left,right=0,a[n-1]
mid=right
while abs(right-left)>2:
    mid=(left+right)//2
    temp=0
    for i in range(n-1,-1,-1):
        if a[i]<=mid: break
        temp+=a[i]//mid
    if temp>k: left=mid
    else: right=mid
mid-=1
if mid<=0: mid=1
while True:
    temp=0
    flag=0
    for i in range(n-1,-1,-1):
        if a[i]<=mid: break
        temp+=a[i]//mid
    if temp>k: mid+=1
    else:
        flag=1
        break
    if flag: break
print(mid)

Submission status: Accepted

Solution code:
"""
                            pppppppppppppppppppp
                         ppppp  ppppppppppppppppppp
                      ppppppp    ppppppppppppppppppppp
                      pppppppp  pppppppppppppppppppppp
                      pppppppppppppppppppppppppppppppp
                              pppppppppppppppppppppppp
       ppppppppppppppppppppppppppppppppppppppppppppppp  pppppppppppppppppppp
      pppppppppppppppppppppppppppppppppppppppppppppppp  ppppppppppppppppppppp
     ppppppppppppppppppppppppppppppppppppppppppppppppp  pppppppppppppppppppppp
    ppppppppppppppppppppppppppppppppppppppppppppppp    pppppppppppppppppppppppp
   pppppppppppppppppppppppppppppppppppppppppppppp     pppppppppppppppppppppppppp
  ppppppppppppppppppppppppppppppppppppppppppppp      pppppppppppppppppppppppppppp
  pppppppppppppppppppppppppppppppp               pppppppppppppppppppppppppppppppp
  pppppppppppppppppppppppppppp     pppppppppppppppppppppppppppppppppppppppppppppp
  ppppppppppppppppppppppppppp    pppppppppppppppppppppppppppppppppppppppppppppppp
    pppppppppppppppppppppppp  pppppppppppppppppppppppppppppppppppppppppppppppppp
     ppppppppppppppppppppppp  ppppppppppppppppppppppppppppppppppppppppppppppppp
      pppppppppppppppppppppp  ppppppppppppppppppppppppppppppppppppppppppppppp
       ppppppppppppppppppppp  ppppppppppppppppppppppppppppppppppppppppppppp
                              pppppppppppppppppppppppp
                              pppppppppppppppppppppppppppppppp
                              pppppppppppppppppppppp  pppppppp
                              ppppppppppppppppppppp    ppppppp
                                 ppppppppppppppppppp  ppppp
                                    pppppppppppppppppppp
"""


import sys
from functools import lru_cache, cmp_to_key
from collections import defaultdict as dd, deque, Counter as C
from bisect import bisect_left as bl, bisect_right as br, bisect
from heapq import heapify, heappop, heappush
# from math import sqrt
from math import ceil, log, floor
mod = pow(10, 9) + 7
mod2 = 998244353
def data(): return sys.stdin.readline().strip()
def out(var, end="\n"): sys.stdout.write(str(var)+end)
def outa(*var, end="\n"): sys.stdout.write(' '.join(map(str, var)) + end)
def L(): return list(sp())
def sl(): return list(ssp())
def sp(): return map(int, data().split())
def ssp(): return map(str, data().split())
def l1d(n, val=0): return [val for i in range(n)]
def l2d(n, m, val=0): return [l1d(n, val) for j in range(m)]


n, k = sp()
arr = L()
low, high = 1, max(arr)
answer = max(arr)
while low <= high:
    mid = (low + high) >> 1
    req = 0
    for i in range(n):
        if arr[i] <= mid:
            continue
        else:
            temp = arr[i] // mid
            req += temp
    if req <= k:
        answer = min(answer, mid)
        high = mid - 1
    else:
        low = mid + 1
out(answer)

Submission status: Accepted

Solution code:
import sys
import math

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    def meguru_bisect(ok, ng):
        """
        is_okを定義して下さい
        :param ok: 取りうる最小の値-1
        :param ng: 取りうる最大の値+1
        :return: is_okを満たす最小(もしくは最大)の値
        """
        while abs(ok - ng) > 10 ** -5:
            mid = (ok + ng) / 2
            if is_ok(mid):
                ok = mid
            else:
                ng = mid
        return ok

    def is_ok(x):
        cnt = 0
        for i in range(n):
            if A[i] > x:
                cnt += (A[i] + x - 1) // x - 1

        return cnt <= k

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

    res = meguru_bisect(10 ** 9 + 1, 0)
    print(math.ceil(res))


if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
from math import ceil

N, K, *A = map(int, open(0).read().split())

def is_ok(n):
    t = 0
    for a in A:
        if a <= n:
            continue
        t += ceil(a / n) - 1
    return t <= K

ok = 1000000000
ng = 0.0000000001
while abs(ng - ok) > 1:
    m = (ok + ng) // 2
    if is_ok(m):
        ok = m
    else:
        ng = m

print(ceil(ok))

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
L=list(map(int,input().split()))
    
import math
MAX=10**9
MIN=0
for i in range(100):
    Mid=(MAX+MIN)/2
    cnt=0
    for j in range(N):
        cnt+=L[j]//Mid
    if cnt<=K:
        MAX=Mid
    else:
        MIN=Mid
    #print(cnt)
print(math.ceil(Mid))

Submission status: Accepted

Solution code:
import math

from sys import stdin
input = stdin.readline


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

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

  def solve(L):
    ncut = 0
    for i in range(N):
      ncut += (math.ceil(A[i]/L) - 1)
      # ncut += math.floor(A[i]/L)
      if ncut > K:
        return False
    return True

  ok = 10**9
  ng = 0
  while abs(ok - ng) > 1:
    mid = (ok + ng) // 2
    bool_ = solve(mid)
    # print(mid, bool_)
    if bool_:
      ok = mid
    else:
      ng = mid

  print(ok)


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