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:
# ---------------------------iye ha aam zindegi---------------------------------------------
import math
import heapq, bisect
import sys
from collections import deque, defaultdict
from fractions import Fraction
import sys
mod = 10 ** 9 + 7
mod1 = 998244353

# ------------------------------warmup----------------------------
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")


# -------------------game starts now----------------------------------------------------import math
class TreeNode:
    def __init__(self, k, v):
        self.key = k
        self.value = v
        self.left = None
        self.right = None
        self.parent = None
        self.height = 1
        self.num_left = 1
        self.num_total = 1


class AvlTree:

    def __init__(self):
        self._tree = None

    def add(self, k, v):
        if not self._tree:
            self._tree = TreeNode(k, v)
            return
        node = self._add(k, v)
        if node:
            self._rebalance(node)

    def _add(self, k, v):
        node = self._tree
        while node:
            if k < node.key:
                if node.left:
                    node = node.left
                else:
                    node.left = TreeNode(k, v)
                    node.left.parent = node
                    return node.left
            elif node.key < k:
                if node.right:
                    node = node.right
                else:
                    node.right = TreeNode(k, v)
                    node.right.parent = node
                    return node.right
            else:
                node.value = v
                return

    @staticmethod
    def get_height(x):
        return x.height if x else 0

    @staticmethod
    def get_num_total(x):
        return x.num_total if x else 0

    def _rebalance(self, node):

        n = node
        while n:
            lh = self.get_height(n.left)
            rh = self.get_height(n.right)
            n.height = max(lh, rh) + 1
            balance_factor = lh - rh
            n.num_total = 1 + self.get_num_total(n.left) + self.get_num_total(n.right)
            n.num_left = 1 + self.get_num_total(n.left)

            if balance_factor > 1:
                if self.get_height(n.left.left) < self.get_height(n.left.right):
                    self._rotate_left(n.left)
                self._rotate_right(n)
            elif balance_factor < -1:
                if self.get_height(n.right.right) < self.get_height(n.right.left):
                    self._rotate_right(n.right)
                self._rotate_left(n)
            else:
                n = n.parent

    def _remove_one(self, node):
        """
        Side effect!!! Changes node. Node should have exactly one child
        """
        replacement = node.left or node.right
        if node.parent:
            if AvlTree._is_left(node):
                node.parent.left = replacement
            else:
                node.parent.right = replacement
            replacement.parent = node.parent
            node.parent = None
        else:
            self._tree = replacement
            replacement.parent = None
        node.left = None
        node.right = None
        node.parent = None
        self._rebalance(replacement)

    def _remove_leaf(self, node):
        if node.parent:
            if AvlTree._is_left(node):
                node.parent.left = None
            else:
                node.parent.right = None
            self._rebalance(node.parent)
        else:
            self._tree = None
        node.parent = None
        node.left = None
        node.right = None

    def remove(self, k):
        node = self._get_node(k)
        if not node:
            return
        if AvlTree._is_leaf(node):
            self._remove_leaf(node)
            return
        if node.left and node.right:
            nxt = AvlTree._get_next(node)
            node.key = nxt.key
            node.value = nxt.value
            if self._is_leaf(nxt):
                self._remove_leaf(nxt)
            else:
                self._remove_one(nxt)
            self._rebalance(node)
        else:
            self._remove_one(node)

    def get(self, k):
        node = self._get_node(k)
        return node.value if node else -1

    def _get_node(self, k):
        if not self._tree:
            return None
        node = self._tree
        while node:
            if k < node.key:
                node = node.left
            elif node.key < k:
                node = node.right
            else:
                return node
        return None

    def get_at(self, pos):
        x = pos + 1
        node = self._tree
        while node:
            if x < node.num_left:
                node = node.left
            elif node.num_left < x:
                x -= node.num_left
                node = node.right
            else:
                return (node.key, node.value)
        raise IndexError("Out of ranges")

    @staticmethod
    def _is_left(node):
        return node.parent.left and node.parent.left == node

    @staticmethod
    def _is_leaf(node):
        return node.left is None and node.right is None

    def _rotate_right(self, node):
        if not node.parent:
            self._tree = node.left
            node.left.parent = None
        elif AvlTree._is_left(node):
            node.parent.left = node.left
            node.left.parent = node.parent
        else:
            node.parent.right = node.left
            node.left.parent = node.parent
        bk = node.left.right
        node.left.right = node
        node.parent = node.left
        node.left = bk
        if bk:
            bk.parent = node
        node.height = max(self.get_height(node.left), self.get_height(node.right)) + 1
        node.num_total = 1 + self.get_num_total(node.left) + self.get_num_total(node.right)
        node.num_left = 1 + self.get_num_total(node.left)

    def _rotate_left(self, node):
        if not node.parent:
            self._tree = node.right
            node.right.parent = None
        elif AvlTree._is_left(node):
            node.parent.left = node.right
            node.right.parent = node.parent
        else:
            node.parent.right = node.right
            node.right.parent = node.parent
        bk = node.right.left
        node.right.left = node
        node.parent = node.right
        node.right = bk
        if bk:
            bk.parent = node
        node.height = max(self.get_height(node.left), self.get_height(node.right)) + 1
        node.num_total = 1 + self.get_num_total(node.left) + self.get_num_total(node.right)
        node.num_left = 1 + self.get_num_total(node.left)

    @staticmethod
    def _get_next(node):
        if not node.right:
            return node.parent
        n = node.right
        while n.left:
            n = n.left
        return n


# -----------------------------------------------binary seacrh tree---------------------------------------
class SegmentTree1:
    def __init__(self, data, default='z', func=lambda a, b: min(a, b)):
        """initialize the segment tree with data"""
        self._default = default
        self._func = func
        self._len = len(data)
        self._size = _size = 1 << (self._len - 1).bit_length()

        self.data = [default] * (2 * _size)
        self.data[_size:_size + self._len] = data
        for i in reversed(range(_size)):
            self.data[i] = func(self.data[i + i], self.data[i + i + 1])

    def __delitem__(self, idx):
        self[idx] = self._default

    def __getitem__(self, idx):
        return self.data[idx + self._size]

    def __setitem__(self, idx, value):
        idx += self._size
        self.data[idx] = value
        idx >>= 1
        while idx:
            self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
            idx >>= 1

    def __len__(self):
        return self._len

    def query(self, start, stop):
        if start == stop:
            return self.__getitem__(start)
        stop += 1
        start += self._size
        stop += self._size

        res = self._default
        while start < stop:
            if start & 1:
                res = self._func(res, self.data[start])
                start += 1
            if stop & 1:
                stop -= 1
                res = self._func(res, self.data[stop])
            start >>= 1
            stop >>= 1
        return res

    def __repr__(self):
        return "SegmentTree({0})".format(self.data)


# -------------------game starts now----------------------------------------------------import math
class SegmentTree:
    def __init__(self, data, default=0, func=lambda a, b: a + b):
        """initialize the segment tree with data"""
        self._default = default
        self._func = func
        self._len = len(data)
        self._size = _size = 1 << (self._len - 1).bit_length()

        self.data = [default] * (2 * _size)
        self.data[_size:_size + self._len] = data
        for i in reversed(range(_size)):
            self.data[i] = func(self.data[i + i], self.data[i + i + 1])

    def __delitem__(self, idx):
        self[idx] = self._default

    def __getitem__(self, idx):
        return self.data[idx + self._size]

    def __setitem__(self, idx, value):
        idx += self._size
        self.data[idx] = value
        idx >>= 1
        while idx:
            self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
            idx >>= 1

    def __len__(self):
        return self._len

    def query(self, start, stop):
        if start == stop:
            return self.__getitem__(start)
        stop += 1
        start += self._size
        stop += self._size

        res = self._default
        while start < stop:
            if start & 1:
                res = self._func(res, self.data[start])
                start += 1
            if stop & 1:
                stop -= 1
                res = self._func(res, self.data[stop])
            start >>= 1
            stop >>= 1
        return res

    def __repr__(self):
        return "SegmentTree({0})".format(self.data)


# -------------------------------iye ha chutiya zindegi-------------------------------------
class Factorial:
    def __init__(self, MOD):
        self.MOD = MOD
        self.factorials = [1, 1]
        self.invModulos = [0, 1]
        self.invFactorial_ = [1, 1]

    def calc(self, n):
        if n <= -1:
            print("Invalid argument to calculate n!")
            print("n must be non-negative value. But the argument was " + str(n))
            exit()
        if n < len(self.factorials):
            return self.factorials[n]
        nextArr = [0] * (n + 1 - len(self.factorials))
        initialI = len(self.factorials)
        prev = self.factorials[-1]
        m = self.MOD
        for i in range(initialI, n + 1):
            prev = nextArr[i - initialI] = prev * i % m
        self.factorials += nextArr
        return self.factorials[n]

    def inv(self, n):
        if n <= -1:
            print("Invalid argument to calculate n^(-1)")
            print("n must be non-negative value. But the argument was " + str(n))
            exit()
        p = self.MOD
        pi = n % p
        if pi < len(self.invModulos):
            return self.invModulos[pi]
        nextArr = [0] * (n + 1 - len(self.invModulos))
        initialI = len(self.invModulos)
        for i in range(initialI, min(p, n + 1)):
            next = -self.invModulos[p % i] * (p // i) % p
            self.invModulos.append(next)
        return self.invModulos[pi]

    def invFactorial(self, n):
        if n <= -1:
            print("Invalid argument to calculate (n^(-1))!")
            print("n must be non-negative value. But the argument was " + str(n))
            exit()
        if n < len(self.invFactorial_):
            return self.invFactorial_[n]
        self.inv(n)  # To make sure already calculated n^-1
        nextArr = [0] * (n + 1 - len(self.invFactorial_))
        initialI = len(self.invFactorial_)
        prev = self.invFactorial_[-1]
        p = self.MOD
        for i in range(initialI, n + 1):
            prev = nextArr[i - initialI] = (prev * self.invModulos[i % p]) % p
        self.invFactorial_ += nextArr
        return self.invFactorial_[n]


class Combination:
    def __init__(self, MOD):
        self.MOD = MOD
        self.factorial = Factorial(MOD)

    def ncr(self, n, k):
        if k < 0 or n < k:
            return 0
        k = min(k, n - k)
        f = self.factorial
        return f.calc(n) * f.invFactorial(max(n - k, k)) * f.invFactorial(min(k, n - k)) % self.MOD


# --------------------------------------iye ha combinations ka zindegi---------------------------------
def powm(a, n, m):
    if a == 1 or n == 0:
        return 1
    if n % 2 == 0:
        s = powm(a, n // 2, m)
        return s * s % m
    else:
        return a * powm(a, n - 1, m) % m


# --------------------------------------iye ha power ka zindegi---------------------------------
def sort_list(list1, list2):
    zipped_pairs = zip(list2, list1)

    z = [x for _, x in sorted(zipped_pairs)]

    return z


# --------------------------------------------------product----------------------------------------
def product(l):
    por = 1
    for i in range(len(l)):
        por *= l[i]
    return por


# --------------------------------------------------binary----------------------------------------
def binarySearchCount(arr, n, key):
    left = 0
    right = n - 1

    count = 0

    while (left <= right):
        mid = int((right + left) / 2)

        # Check if middle element is
        # less than or equal to key
        if (arr[mid] < key):
            count = mid + 1
            left = mid + 1

        # If key is smaller, ignore right half
        else:
            right = mid - 1

    return count


# --------------------------------------------------binary----------------------------------------
def countdig(n):
    c = 0
    while (n > 0):
        n //= 10
        c += 1
    return c
def binary(x, length):
    y = bin(x)[2:]
    return y if len(y) >= length else "0" * (length - len(y)) + y

def countGreater(arr, n, k):
    l = 0
    r = n - 1

    # Stores the index of the left most element
    # from the array which is greater than k
    leftGreater = n

    # Finds number of elements greater than k
    while (l <= r):
        m = int(l + (r - l) / 2)
        if (arr[m] >= k):
            leftGreater = m
            r = m - 1

        # If mid element is less than
        # or equal to k update l
        else:
            l = m + 1

    # Return the count of elements
    # greater than k
    return (n - leftGreater)


# --------------------------------------------------binary------------------------------------
n,k=map(int,input().split())
l=list(map(int,input().split()))
if k==0:
    print(max(l))
    sys.exit(0)
def check(mid):
    tot=0
    if mid==0:
        return False
    for i in range(n):
        tot+=math.ceil(l[i]/mid)-1
    if tot<=k:
        return True
    else:
        return False
st=min(l)//(k+1)
end=max(l)
ans=max(l)
while(st<=end):
    mid=(st+end)//2
    #print(mid)
    if check(mid)==True:
        ans=mid
        end=mid-1
    else:
        st=mid+1
print(ans)

Submission status: Accepted

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

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

def check(x):
    res = 0
    for i in a:
        res += math.floor(i / x)
    return res

l = 0
r = 10 ** 9 + 1
for _ in range(100):
    x = (l + r) / 2
    if check(x) > k:
        l = x
    else:
        r = x
print(math.ceil(l))

Submission status: Accepted

Solution code:
import sys

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

A.sort()
if K == 0:
    print(A[-1])
else:
    ans = 10**9
    l = 0
    r = 10**9
    while l < r:
        # t以下の長さにするのに必要な切る回数
        t = (l + r) // 2
        if t == 0:
            break
        # print(t)
        n = K
        for a in A:
            n -= (a - 1) // t
            if n < 0:
                break
        if n >= 0:
            ans = min(ans, t)
        if n >= 0:
            r = t
        else:
            l = t + 1

    print(ans)

Submission status: Accepted

Solution code:
import math

def can_split(a, t, k):
    m = 0
    for x in a:
        m += math.ceil(x / t) - 1
    return m <= k

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

min_val = 10 ** 9
l, r = 0, max(a)
while l + 1 < r:
    m = (l + r) // 2
    if can_split(a, m, k):
        r = m
    else:
        l = m
print (r)

Submission status: Accepted

Solution code:
#import numpy as np
import math
#from decimal import *
#from numba import njit

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

    def check(x):
        if x <= 0:
            return False
        else:
            return N+K >= sum(map(lambda a: math.ceil(a/x), A))

    s = max(A)//2
    h = s//2
    c = check(s)
    last = c
    while True:
        if c:
            s -= max(1,h)
        else:
            s += max(1,h)
        h //= 2
        last = c
        c = check(s)
        if h <= 0 and last != c:
            if last:
                s += 1
            break
    print(s)

main()

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
A = list(map(int,input().split()))
A.sort()
def f(A,N):
    ans = 0
    for i in range(len(A)):
        ans += -(-A[i]//N) - 1
    return ans
ok = 10000000000
ng = 0
while abs(ok-ng) > 1:
    mid = (ok+ng) // 2
    if f(A,mid) <= K:
        ok = mid
    else:
        ng = mid
print(ok)

Submission status: Accepted

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

import math

def num_cuts(A, ml):
	ret = 0
	for a in A:
		ret += (math.ceil(a / ml) - 1)
	return ret

def ok(A, ml):
	return num_cuts(A, ml) <= K

def ans(A, K):

	low = min(A) / (K+5)
	high = max(A)+1

	assert(not(ok(A, low)))
	assert(ok(A, high))

	while (high - low) > 0.1:
		mid = (low + high) / 2
		if ok(A, mid):
			high = mid
		else:
			low = mid

	low = max(1, math.floor(low) - 5)

	for i in range(100):
		p = low + i/2
		if ok(A, p):
			return math.ceil(p)

	assert(False)


N, K = input().split()
N = int(N)
K = int(K)

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

print(ans(A, K))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000000)
import math
from math import gcd
def lcm(a, b): return a * b // gcd(a, b)
from itertools import count, permutations, chain, product
from functools import lru_cache
from collections import deque, defaultdict
from pprint import pprint
ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
INF = float('inf')
N1097 = 10**9 + 7

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

def get_inv(n, modp):
    return pow(n, modp-2, modp)

def factorials_list(n, modp):    # 10**6
    fs = [1]
    for i in range(1, n+1):
        fs.append(fs[-1] * i % modp)
    return fs

def invs_list(n, fs, modp):     # 10**6
    invs = [get_inv(fs[-1], modp)]
    for i in range(n, 1-1, -1):
        invs.append(invs[-1] * i % modp)
    invs.reverse()
    return invs

def comb(n, k, modp):
    num = 1
    for i in range(n, n-k, -1):
        num = num * i % modp
    den = 1
    for i in range(2, k+1):
        den = den * i % modp
    return num * get_inv(den, modp) % modp

def comb_from_list(n, k, modp, fs, invs):
    return fs[n] * invs[n-k] * invs[k] % modp

#

class UnionFindEx:
    def __init__(self, size):
        #正なら根の番号、負ならグループサイズ
        self.roots = [-1] * size
    def getRootID(self, i):
        r = self.roots[i]
        if r < 0:   #負なら根
            return i
        else:
            r = self.getRootID(r)
            self.roots[i] = r
            return r
    def getGroupSize(self, i):
        return -self.roots[self.getRootID(i)]
    def connect(self, i, j):
        r1, r2 = self.getRootID(i), self.getRootID(j)
        if r1 == r2:
            return False
        if self.getGroupSize(r1) < self.getGroupSize(r2):
            r1, r2 = r2, r1
        self.roots[r1] += self.roots[r2]    #サイズ更新
        self.roots[r2] = r1
        return True

Yes = 'Yes'
No = 'No'


from collections import deque

def main():
    '''
    l > A / 3
    3 > A / l
    '''
    N, K = mis()
    A = lmis()
    def f(l):
        k = 0
        for a in A:
            if a%l == 0:
                k += a//l - 1
            else:
                k += a//l
            if k > K:
                return False
        return True

    L = meg(f, 10**10, 0)
    print(L)



main()

Submission status: Accepted

Solution code:
def is_good(mid, key):
    return sum(count_cuts(a, mid) for a in A) <= key


def binary_search(key):
    bad, good = 0, 2 * 10 ** 14 + 1
    while good - bad > 1:
        mid = (bad + good) // 2
        if is_good(mid, key):
            good = mid
        else:
            bad = mid
    return good


def count_cuts(a, unit):
    return (a + unit - 1) // unit - 1


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

Submission status: Accepted

Solution code:
import copy
import math

def calc(x, aa):
    a = copy.deepcopy(aa)
    cnt = k
    while cnt > 0:
        for i in range(n):
            if (a[i] > x):
                cnt -= a[i] // x
                a[i] = x
            if cnt < 0:
                return False
        if cnt < 0:
            return False
        return True
    
n, k = map(int, input().split())
a = [int(i) for i in input().split()]
left, right = 0, max(a)
if k == 0:
    print(right)
    exit()
    
while (right - left) > 1:
    middle = (left + right) / 2
    if calc(middle, a):
        right = middle
    else:
        left = middle        
for i in range(max(math.floor(left) - 10, 1), math.ceil(right) + 10):
    if calc(i, a):
        print(i)
        exit()

Submission status: Accepted

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



sho=1
dai=max(a)
for jfdlas in range(100):
    now=(sho+dai)//2
    gokei=0
    for i in range(n):
        gokei+=(a[i]-1)//now
        #print(gokei)
        if(gokei>k):
            sho=now
            continue
    if(gokei<=k):
        dai=now
    else:
        sho=now
    #print(now,gokei,sho,dai)


print(dai)
#gokei=0
#for i in range(n):
#    gokei+=(a[i]-1)//
#if(gokei>k):
#    print(sho)
#else:
#    print(dai)

Submission status: Accepted

Solution code:
def get_cuts_nr(loglens, ln):
    ans = 0
    for log in loglens:
        ans += (log - 1) // ln
    # print(ans)
    return ans

def solvee():
    n, k = (int(x) for x in input().split())
    loglens = [int(x) for x in input().split()]

    l_op = 0
    r_cl = 10 ** 9 + 5
    while r_cl - l_op > 1:
        m = (l_op + r_cl) // 2
        cuts_nr = get_cuts_nr(loglens, m)
        if cuts_nr > k:
            l_op = m
        else:
            r_cl = m
    # assert r_cl == 292638192
    print(r_cl)


if __name__ == '__main__':
    solvee()

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
alist=list(map(int,input().split()))
#print(alist)

def num_cut(x):
  if x==0:
    return float("inf")
  
  ret=0
  for a in alist:
    ret+=-(-(a-x)//x)
  return ret

#for i in range(1,max(alist)):
#  print(i,num_cut(i))

l=1
r=max(alist)+1
while l<=r:
  mid=(l+r)//2
  #print(l,mid,r)
  
  if num_cut(mid-1)>K and num_cut(mid)<=K:
    print(mid)
    break
  elif num_cut(mid)<=K:
    r=mid
  else:
    l=mid

Submission status: Accepted

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

s, e = 1, 100000000000

while s <= e:
   # print(s, e)
    mid = (s+e)//2
    temp = 0
    for x in arr:
        temp += x//mid
        if x%mid == 0:
            temp -= 1
    #print(temp)
    if temp <= k:
        ans = mid
        e = mid-1
    else:
        s = mid+1

print(ans)

Submission status: Accepted

Solution code:
import math


def f(A, m, K):
    p = sum([a // m for a in A])
    if p > K:
        return False
    else:
        return True


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


left = 0
right = 10 ** 9 + 1

while int(left) != int(right):
    m = (left + right) / 2

    if f(A, m, K):
        right = m
    else:
        left = m


print(math.ceil(m))

Submission status: Accepted

Solution code:
import math

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

K += N
sum_ = sum(a_list)

ideal_d = [(K / sum_) * a for a in a_list]
min_d = [math.floor(i_d) if math.floor(i_d) != 0 else 1 for i_d in ideal_d]

max_ded_a_list = [a/m_d for a, m_d in zip(a_list, min_d) ]
min_ded_a_list = [a/(m_d+1) for a, m_d in zip(a_list, min_d)]
num_replace = K - sum(min_d)
max_ded_a_list.sort(reverse=True)

ans = math.ceil(max_ded_a_list[num_replace])
print(ans)

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

#############
# Main Code #
#############

N, K = getNM()
A = getList()

# 単純に大きいのを1 / 2していては
# 3.5, 3.5, 4.5, 2.25, 2.25ができるのでダメ

# Kがばか大きい

def f(target):
    cnt = 0
    for i in range(N):
        cnt += math.ceil(A[i] / target) - 1
    if cnt <= K:
        return True
    else:
        return False

ng = 0
ok = 10 ** 9 + 1
for i in range(100):
    mid = (ng + ok) / 2
    # midがでかすぎるなら上限を下げる
    if f(mid):
        ok = mid
    # midが小さすぎるなら下限を上げる
    else:
        ng = mid
print(math.ceil(ok))

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**6)
    N, K = [int(x) for x in input().strip().split()]
    A = [int(x) for x in input().strip().split()]
    l, r = 0, max(A)
    def f(m):
        ret = 0
        # print('m={}'.format(m))
        for a in A:
            ret += (a // m) - 1 + (a % m > 0)
            if ret > K:
                return False
        return True

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from sys import stdin
from sys import setrecursionlimit
import numpy as np
import math

setrecursionlimit(10 ** 7)

n,k = map(int,stdin.readline().rstrip().split())
a = list(map(int,stdin.readline().rstrip().split()))

a.sort()
a = np.array(a,dtype=np.int64)

low = 0
hi = 10**9
point = 0

while point <= 100:
    ave = (hi+low)/2
    if np.ceil(a//ave).sum() <= k:
        hi = ave
    else:
        low = ave
    point += 1

print(math.ceil(ave))

Submission status: Accepted

Solution code:
BIG = 10**10

N, K = map(int, input().split())
A = list(map(int, input().split()))
# N, K = 2*10**5, 2*10**5
# A = [10**9]*N

def solve(x):
    m = 0
    for a in A:
        m += -(-(a//x))
    # print(x, m)
    return m > K

A = [a*BIG for a in A]

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

# print(c)

print(-(-ok//BIG))