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: Runtime Error

Solution code:
nk=input("").split(" ")
n=int(nk[0])
k=int(nk[1])
lia=input("").split(" ")
lisa=[]
for i in lia:
    lisa+=[int(i)*10000]
sa=sum(lisa)
lisf=[]
lisw=[]
t=int(sa/(k+1))
for i in lisa:
    f=i%t
    ffff=(i*(k+1))%sa
    
    if(ffff==0):
        lisf+=[0]
        lisw+=[int(i*(k+1)/sa)-1]
    else:
        lisf+=[(t-f)/(int(i*(k+1)/sa)+1)]
        lisw+=[int(i*(k+1)/sa)]

lisf.sort()
s=k-sum(lisw)

kk=int((t-lisf[s])/10000)
if(((t-lisf[s])%10000)==0):
    print(kk)
else:
    print(kk+1)

Submission status: Runtime Error

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

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

Submission status: Runtime Error

Solution code:
n,k=map(int,input().split())
a=sorted(list(map(int,input().split())))
def cal(x,p):
    if x<=p:
        return 0
    else:
        ret=0
        if x%2==0:
            ret=cal(x//2,p)*2+1
        else:
            ret=cal(x//2,p)+cal(x//2+1,p)+1
        return ret
num=max(a)//2
left=0
right=max(a)
flag=1
ans=num
if k==0:
    print(max(a))
    exit()
while flag!=0:
    s=0
    for i in range(n):
        s+=cal(a[i],num)
    if k>=s:
        ans=min(ans,num)
        if ans+1==num:
            flag=0
        elif ans==num:
            flag=0
        right=num
        num=(left+right)//2
    else:
        left=num
        num=(right+left)//2
print(ans)

Submission status: Runtime Error

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

while K >= 0:
    A.sort()
    k = A[-1] // A[-2]
    if K-k >= 0:
        tmp = A[-1] / (k+1)
        A.pop(-1)
        A.extend([tmp]*(int(k+1)))
        K -= k
    else:
        break
print(int(max(A)))

Submission status: Runtime Error

Solution code:
import heapq
N,K = map(int,input().split())
A = list(map(lambda x:int(x)*(-1),input().split()))
heapq.heapify(A)
for _ in range(K):
    maxi = heapq.heappop(A)
    maxi2 = heapq.heappop(A)
    #print(maxi,maxi2)
    if maxi==maxi2:
        heapq.heappush(A,maxi/2)
        heapq.heappush(A,maxi/2)
        heapq.heappush(A,maxi2)
    else:
        heapq.heappush(A,maxi2)
        heapq.heappush(A,maxi2)
        heapq.heappush(A,maxi-maxi2)
ans = heapq.heappop(A)
print(-ans)

Submission status: Runtime Error

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
aa=sum(a)/(k+n)
ans=[1]
ans*=n
for i in range(n):
    ans[i]=a[i]//aa
aaa=k+n-sum(ans)
for i in range(n):
    a[i]/=ans[i]
a.sort(reverse=True)
aaa=int(aaa)
if a[aaa]>int(a[aaa]):
    a[aaa]+=1
print(int(a[aaa]))

Submission status: Runtime Error

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

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


# めぐる式二部探索
l=-1
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:
            cnt-=a[i]//mid
            if cnt<0:
                flag=False
                break
    # なんらかの判定
    if flag:
        r = mid  # 判定がOKのとき→範囲を左に狭める
    else:
        l = mid  # 判定がNGのとき→範囲を右に狭める

print(r)

Submission status: Runtime Error

Solution code:
nk=input("").split(" ")
n=int(nk[0])
k=int(nk[1])
lia=input("").split(" ")
lisa=[]
for i in lia:
    lisa+=[int(i)*10000]
sa=sum(lisa)
lisf=[]
lisw=[]
t=int(sa/(k+1))
for i in lisa:
    f=i%t
    ffff=(i*(k+1))%sa
    
    if(ffff==0):
        lisf+=[0]
        lisw+=[int(i*(k+1)/sa)-1]
    else:
        lisf+=[(t-f)/(int(i*(k+1)/sa)+1)]
        lisw+=[int(i*(k+1)/sa)]

lisf.sort()
s=k-sum(lisw)

kk=int((t-lisf[s])/10000)
if(abs((t-lisf[s])%10000)<2):
    print(kk)
else:
    print(kk+1)

Submission status: Runtime Error

Solution code:
import heapq
from math import ceil
import sys

class Fraction():
    ##入力定義
    def __init__(self,Numerator=0,Denominator=1):
        """分数のオブジェクトを生成する.

        Numerator:分子
        Denominator:分母
        """
        self.a=Numerator
        self.b=Denominator

    #表示定義
    def __str__(self):
        if self.b==1:
            return str(self.a)
        else:
            return "{}/{}".format(self.a,self.b)

    #四則演算定義
    def __add__(self,other):
        c=Fraction()
        if not(isinstance(other,Fraction)):
            other=Fraction.Int_to_Fraction(other)
            
        c.a=self.a*other.b+self.b*other.a
        c.b=self.b*other.b
        return Fraction.__reduce(c)

    def __radd__(self,other):
        c=Fraction()
        if not(isinstance(other,Fraction)):
            other=Fraction.Int_to_Fraction(other)
            
        c.a=self.a*other.b+self.b*other.a
        c.b=self.b*other.b
        
        return Fraction.__reduce(c)
    
    def __sub__(self,other):
        return self+(-other)

    def __rsub__(self,other):
        return -self+other

    def __mul__(self,other):
        if not(isinstance(other,Fraction)):
            other=Fraction.Int_to_Fraction(other)
            
        return Fraction.__reduce(Fraction(self.a*other.a,self.b*other.b))

    def __rmul__(self,other):
        if not(isinstance(other,Fraction)):
            other=Fraction.Int_to_Fraction(other)
            
        return Fraction.__reduce(Fraction(self.a*other.a,self.b*other.b))

    def __floordiv__(self,other):
        if other==Fraction():
            raise ZeroDivisionError
        
        H=self/other
        return H.a//H.b

    def __rfloordiv__(self,other):
        if self==Fraction():
            raise ZeroDivisionError

        H=other/self
        return H.a//H.b
    
    def __truediv__(self,other):
        if other==Fraction():
            raise ZeroDivisionError
        
        if not(isinstance(other,Fraction)):
            other=Fraction.Int_to_Fraction(other)
            
        return self*Fraction.__inverse(other)

    def __rtruediv__(self,other):
        if self==Fraction():
            raise ZeroDivisionError
        
        if not(isinstance(self,Fraction)):
            self=Fraction.Int_to_Fraction(other)
            
        return Fraction.__inverse(self)*other

    def __pow__(self,other):
        if other==0:
            return 1
        n=abs(other)

        g=1
        k=self
        for i in range(int(math.log(n,2))+1):
            if n%2==1:
                g*=k

            k*=k
            n=n>>1

        if other>0:
            return g
        else:
            return 1/g

    #丸め
    def __floor__(self):
        return self.a//self.b

    def __ceil__(self):
        return (self.a+self.b-1)//self.b
    
    #比較演算子
    def __eq__(self,other):
        t=self-other
        if isinstance(t,Fraction):
            return t.a==0
        else:
            return t==0
    
    def __nq(self,other):
        return not(self==other)

    def __lt__(self,other):
        t=self-other
        if isinstance(t,Fraction):
            return t.a<0
        else:
            return t<0

    def __le__(self,other):
        return (self<other) or (self==other)

    def __gt__(self,other):
        return -self<-other

    def __ge__(self,other):
        return (other<self) or (self==other)
    
    #その他
    def ToNumber(self):
        return self.a/self.b

    def sign(self):
        s=self.a*self.b
        if s>0:return 1
        elif s==0:return 0
        else:return -1

    def __reduce(self):
        from math import gcd
        g=gcd(self.a,self.b)
        self.a//=g
        self.b//=g

        if self.b<0:
            self.a*=-1
            self.b*=-1
        return Fraction(self.a,self.b)

    def Int_to_Fraction(self):
        if not(isinstance(self,Fraction)):
            return Fraction(self,1)
        else:return self
        
    def __inverse(self):
        if self==Fraction():
            raise ZeroDivisionError
        
        return Fraction.__reduce(Fraction(self.b,self.a))
    
    def __pos__(self):
        return self

    def __neg__(self):
        return Fraction(-self.a,self.b)

    def __abs__(self):
        return max(self,-self)
#=======================================
N,K=map(int,input().split())
A=list(map(lambda x:-Fraction(int(x),1),input().split()))

if N==1:
    print((-A[0]+K)//(K+1))
    sys.exit()
    
heapq.heapify(A)
while K>0:
    x=-heapq.heappop(A)

    if x<1:
        heapq.heappush(A,-a)
        break
    y=-heapq.heappop(A)

    J=max((-x.a-1)//x.b,1)
    M=min(max(ceil(x.a/y-x.b),ceil(x.a/J-x.b),1),K)
    x.b+=M
    K-=M
    heapq.heappush(A,-x)
    heapq.heappush(A,-y)

b=-A[0]
b=ceil(b)
print(b)

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
rule=input().split()
N=int(rule[0])
K=int(rule[1])
data=input().split()
ans=0
for i in range(len(data)):
    ans+=int(data[i])
import math
print(math.ceil(ans/K))

Submission status: Runtime Error

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




# めぐる式二部探索
l=-1
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:
            cnt-=a[i]//mid
            if cnt<0:
                flag=False
                break
    # なんらかの判定
    if flag:
        r = mid  # 判定がOKのとき→範囲を左に狭める
    else:
        l = mid  # 判定がNGのとき→範囲を右に狭める

print(r)

Submission status: Runtime Error

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

import heapq
heapq.heapify(A)

while K:
    a = heapq.heappop(A)
    b = heapq.heappop(A)
    a, b = a*-1, b*-1
    c = (b+1)//2
    d = a - c
    heapq.heappush(A, b*-1)
    heapq.heappush(A, c*-1)
    heapq.heappush(A, d*-1)
    K -= 1

print(sorted(A)[0]*-1)

Submission status: Runtime Error

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
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: Runtime Error

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

Submission status: Runtime Error

Solution code:
import heapq
from math import ceil
import sys

class Fraction():
    ##入力定義
    def __init__(self,Numerator=0,Denominator=1):
        """分数のオブジェクトを生成する.

        Numerator:分子
        Denominator:分母
        """
        self.a=Numerator
        self.b=Denominator

    #表示定義
    def __str__(self):
        if self.b==1:
            return str(self.a)
        else:
            return "{}/{}".format(self.a,self.b)

    #四則演算定義
    def __add__(self,other):
        c=Fraction()
        if not(isinstance(other,Fraction)):
            other=Fraction.Int_to_Fraction(other)
            
        c.a=self.a*other.b+self.b*other.a
        c.b=self.b*other.b
        return Fraction.__reduce(c)

    def __radd__(self,other):
        c=Fraction()
        if not(isinstance(other,Fraction)):
            other=Fraction.Int_to_Fraction(other)
            
        c.a=self.a*other.b+self.b*other.a
        c.b=self.b*other.b
        
        return Fraction.__reduce(c)
    
    def __sub__(self,other):
        return self+(-other)

    def __rsub__(self,other):
        return -self+other

    def __mul__(self,other):
        if not(isinstance(other,Fraction)):
            other=Fraction.Int_to_Fraction(other)
            
        return Fraction.__reduce(Fraction(self.a*other.a,self.b*other.b))

    def __rmul__(self,other):
        if not(isinstance(other,Fraction)):
            other=Fraction.Int_to_Fraction(other)
            
        return Fraction.__reduce(Fraction(self.a*other.a,self.b*other.b))

    def __floordiv__(self,other):
        if other==Fraction():
            raise ZeroDivisionError
        
        H=self/other
        return H.a//H.b

    def __rfloordiv__(self,other):
        if self==Fraction():
            raise ZeroDivisionError

        H=other/self
        return H.a//H.b
    
    def __truediv__(self,other):
        if other==Fraction():
            raise ZeroDivisionError
        
        if not(isinstance(other,Fraction)):
            other=Fraction.Int_to_Fraction(other)
            
        return self*Fraction.__inverse(other)

    def __rtruediv__(self,other):
        if self==Fraction():
            raise ZeroDivisionError
        
        if not(isinstance(self,Fraction)):
            self=Fraction.Int_to_Fraction(other)
            
        return Fraction.__inverse(self)*other

    def __pow__(self,other):
        if other==0:
            return 1
        n=abs(other)

        g=1
        k=self
        for i in range(int(math.log(n,2))+1):
            if n%2==1:
                g*=k

            k*=k
            n=n>>1

        if other>0:
            return g
        else:
            return 1/g

    #丸め
    def __floor__(self):
        return self.a//self.b

    def __ceil__(self):
        return (self.a+self.b-1)//self.b
    
    #比較演算子
    def __eq__(self,other):
        t=self-other
        if isinstance(t,Fraction):
            return t.a==0
        else:
            return t==0
    
    def __nq(self,other):
        return not(self==other)

    def __lt__(self,other):
        t=self-other
        if isinstance(t,Fraction):
            return t.a<0
        else:
            return t<0

    def __le__(self,other):
        return (self<other) or (self==other)

    def __gt__(self,other):
        return -self<-other

    def __ge__(self,other):
        return (other<self) or (self==other)
    
    #その他
    def ToNumber(self):
        return self.a/self.b

    def sign(self):
        s=self.a*self.b
        if s>0:return 1
        elif s==0:return 0
        else:return -1

    def __reduce(self):
        from math import gcd
        g=gcd(self.a,self.b)
        self.a//=g
        self.b//=g

        if self.b<0:
            self.a*=-1
            self.b*=-1
        return Fraction(self.a,self.b)

    def Int_to_Fraction(self):
        if not(isinstance(self,Fraction)):
            return Fraction(self,1)
        else:return self
        
    def __inverse(self):
        if self==Fraction():
            raise ZeroDivisionError
        
        return Fraction.__reduce(Fraction(self.b,self.a))
    
    def __pos__(self):
        return self

    def __neg__(self):
        return Fraction(-self.a,self.b)

    def __abs__(self):
        return max(self,-self)
#=======================================
N,K=map(int,input().split())
A=list(map(lambda x:-Fraction(int(x),1),input().split()))

if N==1:
    print((-A[0]+K)//(K+1))
    sys.exit()
    
heapq.heapify(A)
while K>0:
    x=-heapq.heappop(A)

    if x<1:
        heapq.heappush(A,-a)
        break
    y=-heapq.heappop(A)
    
    J=int(-x)
    
    M=min(max(ceil(x.a/y-x.b),ceil(x.a/J-x.b),1),K)
    x.b+=M
    K-=M
    heapq.heappush(A,-x)
    heapq.heappush(A,-y)

b=-A[0]
b=ceil(b)
print(b)

Submission status: Runtime Error

Solution code:
def read():
    N, Q = map(int, input().split(' '))
    cs = list(map(int, input().split(' ')))
    qs = []
    for _ in range(Q):
        l, r = map(int, input().split(' '))
        qs.append((l, r))
    return N, Q, cs, qs


def fun(N, Q, cs, qs):
    for l, r in qs:
        s = set(cs[l-1:r])
        print(len(s))


if __name__ == '__main__':
    N, Q, cs, qs = read()
    fun(N, Q, cs, qs)

Submission status: Runtime Error

Solution code:
nk=input("").split(" ")
n=int(nk[0])
k=int(nk[1])
lia=input("").split(" ")
lisa=[]
for i in lia:
    lisa+=[int(i)*10000]
sa=sum(lisa)
lisf=[]
lisw=[]
t=int(sa/(k+1))
for i in lisa:
    f=i%t
    ffff=(i*(k+1))%sa
    
    if(ffff==0):
        lisf+=[0]
        lisw+=[int(i*(k+1)/sa)-1]
    else:
        lisf+=[(t-f)/(int(i*(k+1)/sa)+1)]
        lisw+=[int(i*(k+1)/sa)]

lisf.sort()
s=k-sum(lisw)
lisf+=[3]*n
kk=int((t-lisf[s])/10000)
if((t-lisf[s])%10000==0):
    print(kk)
else:
    print(kk+1)

Submission status: Runtime Error

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



# めぐる式二部探索
l=-1
r=a[-1]+1
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:
            cnt-=a[i]//mid
            if cnt<0:
                flag=False
                break


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


print(r)

Submission status: Runtime Error

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



# めぐる式二部探索
l=-1
r=a[-1]
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:
            cnt-=a[i]//mid
            if cnt<0:
                flag=False
                break


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


print(r)

Submission status: Runtime Error

Solution code:
import math

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

af = [float(a[i]) for i in range(n)]

s = sum(a)
# a.sort()
# a.reverse()

for i in range(n):
    t = round(k * a[i] / s)
    k -= t
    temp = a[i]
    af[i] = a[i] / (t + 1)
    s -= temp + af[i]

print(math.ceil(max(af)))

Submission status: Runtime Error

Solution code:
nk=input("").split(" ")
n=int(nk[0])
k=int(nk[1])
lia=input("").split(" ")
lisa=[]
for i in lia:
    lisa+=[int(i)*10000]
sa=sum(lisa)
lisf=[]
lisw=[]
t=int(sa/(k+1))
for i in lisa:
    f=i%t
    ffff=(i*(k+1))%sa
    
    if(ffff==0):
        lisf+=[0]
        lisw+=[int(i*(k+1)/sa)-1]
    else:
        lisf+=[(t-f)/(int(i*(k+1)/sa)+1)]
        lisw+=[int(i*(k+1)/sa)]

lisf.sort()
s=k-sum(lisw)
lisf+=[0]
kk=int((t-lisf[s])/10000)
if((t-lisf[s])%10000==0):
    print(kk)
else:
    print(kk+1)

Submission status: Runtime Error

Solution code:
from math import ceil
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=int(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: Runtime Error

Solution code:
import heapq
from math import ceil
import sys

class Fraction():
    ##入力定義
    def __init__(self,Numerator=0,Denominator=1):
        """分数のオブジェクトを生成する.

        Numerator:分子
        Denominator:分母
        """
        self.a=Numerator
        self.b=Denominator

    #表示定義
    def __str__(self):
        if self.b==1:
            return str(self.a)
        else:
            return "{}/{}".format(self.a,self.b)

    #四則演算定義
    def __add__(self,other):
        c=Fraction()
        if not(isinstance(other,Fraction)):
            other=Fraction.Int_to_Fraction(other)
            
        c.a=self.a*other.b+self.b*other.a
        c.b=self.b*other.b
        return Fraction.__reduce(c)

    def __radd__(self,other):
        c=Fraction()
        if not(isinstance(other,Fraction)):
            other=Fraction.Int_to_Fraction(other)
            
        c.a=self.a*other.b+self.b*other.a
        c.b=self.b*other.b
        
        return Fraction.__reduce(c)
    
    def __sub__(self,other):
        return self+(-other)

    def __rsub__(self,other):
        return -self+other

    def __mul__(self,other):
        if not(isinstance(other,Fraction)):
            other=Fraction.Int_to_Fraction(other)
            
        return Fraction.__reduce(Fraction(self.a*other.a,self.b*other.b))

    def __rmul__(self,other):
        if not(isinstance(other,Fraction)):
            other=Fraction.Int_to_Fraction(other)
            
        return Fraction.__reduce(Fraction(self.a*other.a,self.b*other.b))

    def __floordiv__(self,other):
        if other==Fraction():
            raise ZeroDivisionError
        
        H=self/other
        return H.a//H.b

    def __rfloordiv__(self,other):
        if self==Fraction():
            raise ZeroDivisionError

        H=other/self
        return H.a//H.b
    
    def __truediv__(self,other):
        if other==Fraction():
            raise ZeroDivisionError
        
        if not(isinstance(other,Fraction)):
            other=Fraction.Int_to_Fraction(other)
            
        return self*Fraction.__inverse(other)

    def __rtruediv__(self,other):
        if self==Fraction():
            raise ZeroDivisionError
        
        if not(isinstance(self,Fraction)):
            self=Fraction.Int_to_Fraction(other)
            
        return Fraction.__inverse(self)*other

    def __pow__(self,other):
        if other==0:
            return 1
        n=abs(other)

        g=1
        k=self
        for i in range(int(math.log(n,2))+1):
            if n%2==1:
                g*=k

            k*=k
            n=n>>1

        if other>0:
            return g
        else:
            return 1/g

    #丸め
    def __floor__(self):
        return self.a//self.b

    def __ceil__(self):
        return (self.a+self.b-1)//self.b
    
    #比較演算子
    def __eq__(self,other):
        t=self-other
        if isinstance(t,Fraction):
            return t.a==0
        else:
            return t==0
    
    def __nq(self,other):
        return not(self==other)

    def __lt__(self,other):
        t=self-other
        if isinstance(t,Fraction):
            return t.a<0
        else:
            return t<0

    def __le__(self,other):
        return (self<other) or (self==other)

    def __gt__(self,other):
        return -self<-other

    def __ge__(self,other):
        return (other<self) or (self==other)
    
    #その他
    def ToNumber(self):
        return self.a/self.b

    def sign(self):
        s=self.a*self.b
        if s>0:return 1
        elif s==0:return 0
        else:return -1

    def __reduce(self):
        from math import gcd
        g=gcd(self.a,self.b)
        self.a//=g
        self.b//=g

        if self.b<0:
            self.a*=-1
            self.b*=-1
        return Fraction(self.a,self.b)

    def Int_to_Fraction(self):
        if not(isinstance(self,Fraction)):
            return Fraction(self,1)
        else:return self
        
    def __inverse(self):
        if self==Fraction():
            raise ZeroDivisionError
        
        return Fraction.__reduce(Fraction(self.b,self.a))
    
    def __pos__(self):
        return self

    def __neg__(self):
        return Fraction(-self.a,self.b)

    def __abs__(self):
        return max(self,-self)
#=======================================
N,K=map(int,input().split())
A=list(map(lambda x:-Fraction(int(x),1),input().split()))

if N==1:
    print((-A[0]+K)//(K+1))
    sys.exit()
    
heapq.heapify(A)
while K>0:
    x=-heapq.heappop(A)

    if x<1:
        heapq.heappush(A,-a)
        break
    y=-heapq.heappop(A)
    
    M=min(max(ceil(x.a/y-x.b),1),K)
    x.b+=M
    K-=M
    heapq.heappush(A,-x)
    heapq.heappush(A,-y)

b=-A[0]
b=ceil(b)
print(b)

Submission status: Runtime Error

Solution code:
import math
N,K=map(int,input().split())
L = list(map(int, input().split()))
L.sort(reverse=True)
def binary_search(list, item):
    low = 0
    high = L[0]
    while low!=high:
        mid=(low+high)//2
        p=0
        for i in range(len(L)):
            p+=math.ceil(L[i]/mid)-1
        if p==item:
            return mid
        elif p>item:
            low=mid
        else:
            high=mid
if K==0:
    print(L[0])
else:
    print(binary_search(L,K))

Submission status: Runtime Error

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 = math.ceil(sum(A)/(len(A)+K))
for i, a in enumerate(A):
    cut_at_least = (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 <= 3*lenhq:
        heapq.heappush(hq, (-A[i]/(cuts[i]+1), i))
l, i = heapq.heappop(hq)
print(math.ceil(-l))

Submission status: Runtime Error

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 = math.ceil(sum(A)/(len(A)+K))
for i, a in enumerate(A):
    cut_at_least = (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 <= lenhq:
        heapq.heappush(hq, (-A[i]/(cuts[i]+1), i))
l, i = heapq.heappop(hq)
print(math.ceil(-l))

Submission status: Runtime Error

Solution code:
nk=input("").split(" ")
n=int(nk[0])
k=int(nk[1])
lia=input("").split(" ")
lisa=[]
for i in lia:
    lisa+=[int(i)*10000]
sa=sum(lisa)
lisf=[]
lisw=[]
t=int(sa/(k+1))
for i in lisa:
    f=i%t
    ffff=(i*(k+1))%sa
    #print(f)
    #print(ffff)
    if(ffff==0):
        lisf+=[0]
        lisw+=[int(i*(k+1)/sa)-1]
    else:
        lisf+=[(t-f)/(int(i*(k+1)/sa)+1)]
        lisw+=[int(i*(k+1)/sa)]

lisf.sort()
s=k-sum(lisw)
kk=int((t-lisf[s])/10000)
if((t-lisf[s])%10000==0):
    print(kk)
else:
    print(kk+1)