Problem:


Score: 500 points

Problem Statement

Takahashi will take part in an eating contest. Teams of N members will compete in this contest, and Takahashi's team consists of N players numbered 1 through N from youngest to oldest. The consumption coefficient of Member i is A_i.

In the contest, N foods numbered 1 through N will be presented, and the difficulty of Food i is F_i. The details of the contest are as follows:

A team should assign one member to each food, and should not assign the same member to multiple foods.

It will take x \times y seconds for a member to finish the food, where x is the consumption coefficient of the member and y is the difficulty of the dish.

The score of a team is the longest time it takes for an individual member to finish the food.

Before the contest, Takahashi's team decided to do some training. In one set of training, a member can reduce his/her consumption coefficient by 1, as long as it does not go below 0. However, for financial reasons, the N members can do at most K sets of training in total.

What is the minimum possible score of the team, achieved by choosing the amounts of members' training and allocating the dishes optimally?

Constraints

All values in input are integers.

1 \leq N \leq 2 \times 10^5

0 \leq K \leq 10^{18}

1 \leq A_i \leq 10^6\ (1 \leq i \leq N)

1 \leq F_i \leq 10^6\ (1 \leq i \leq N)

Input

Input is given from Standard Input in the following format:

N K
A_1 A_2 ... A_N
F_1 F_2 ... F_N

Output

Print the minimum possible score of the team.

Sample Input 1

3 5
4 2 1
2 3 1

Sample Output 1

2

They can achieve the score of 2, as follows:

Member 1 does 4 sets of training and eats Food 2 in (4-4) \times 3 = 0 seconds.

Member 2 does 1 set of training and eats Food 3 in (2-1) \times 1 = 1 second.

Member 3 does 0 sets of training and eats Food 1 in (1-0) \times 2 = 2 seconds.

They cannot achieve a score of less than 2, so the answer is 2.

Sample Input 2

3 8
4 2 1
2 3 1

Sample Output 2

0

They can choose not to do exactly K sets of training.

Sample Input 3

11 14
3 1 4 1 5 9 2 6 5 3 5
8 9 7 9 3 2 3 8 4 6 2

Sample Output 3

12



Sample input:
3 5
4 2 1
2 3 1


Sample output:
2

Submission status: Accepted

Solution code:
import numpy as np

N,K = list(map(int, input().split(" ")))
A = list(map(int, input().split(" "))) # consumption coefficient of members
F = list(map(int, input().split(" "))) # difficulty of food

# pair fastest eaters (low consumption coefficient) with most difficult foods
A.sort()
F.sort(reverse=True)
A = np.array(A)
F = np.array(F)

maxT = np.max(A*F)
# use binary search to find lowest possible T
left = -1
right = maxT
while left+1< right:
    mid = (left+right)//2
    if np.maximum(0, A - (mid//F)).sum() <= K:
        right  = mid
    else:
        left = mid
print(right)

Submission status: Accepted

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

a_list.sort()
f_list.sort(key=lambda x :-x)

ng = -1
# 完食時間の最大はA=10**6, F=10**6の時。
ok = 10**12+1

def isok(x):
    # 最大の完食時間がxになるように修行する
    # その場合の修行回数の合計を求める
    # そしてそれがK回以下ならTrueを返す
    cnt = 0
    for a, f in zip(a_list,f_list):
        aprime = x // f
        cnt += max(a - aprime,0)
        
        if cnt > K:
            return False
    return True

while abs(ok-ng)>1:
    x = (ok+ng) // 2
    
    if isok(x):
        # train_cntが限界より多い場合、目指す最大の完食時間が短すぎる
        # よって完食時間を増やすべき
        # Kに等しい場合ももしかしたらもっといい
        ok = x
    else:
        ng = x
        
        
print(ok)

Submission status: Accepted

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

def isok(m):
  c = 0
  for i,j in zip(a,f):
    if i*j >= m:
      c += i - m//j
    if c > k:
      return False
  return True

ok = 10**12+1
ng = -1
while abs(ok-ng) > 1:
  m = (ok+ng) // 2
  if isok(m):
    ok = m
  else:
    ng = m
print(ok)

Submission status: Accepted

Solution code:
import sys


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    n, k = list(map(int, readline().split()))
    a = list(map(int, readline().split()))
    a.sort()
    f = list(map(int, readline().split()))
    f.sort(reverse=True)
    af = [av * fv for av, fv in zip(a, f)]

    cor_v = 10 ** 13
    inc_v = -1
    while cor_v - inc_v > 1:
        bin_v = (cor_v + inc_v) // 2
        cost = 0
        #条件を満たすcostを全検索
        for i, v in enumerate(af):
            if v > bin_v:
                cost += ((v - bin_v) + f[i] - 1) // f[i]
        #costが制約を満たすか
        if cost <= k:
            cor_v = bin_v
        else:
            inc_v = bin_v
    print(cor_v)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
from math import ceil
 
N, K = map(int,input().split())
A = sorted([int(i) for i in input().split()])
F = sorted([int(i) for i in input().split()],reverse=True)
# メンバーそれぞれが完食にかかる時間のリスト
cost = [A[i]*F[i] for i in range(N)]
 
# K回の修行でチーム成績がxになるか
def grade_is_x(x):
    training = 0
    for i in range(N):
        if cost[i] > x:
            training += ceil((cost[i]-x)/F[i])
            if training > K:
                return False
    return True
 
# 二分探索でxの最小値を求める
cost_max = max(cost)
ok = cost_max
ng = max(-1,max(cost)-K*F[cost.index(cost_max)])
while (ok - ng) != 1:
    mid = (ok + ng) // 2
    if grade_is_x(mid):
        ok = mid
    else:
        ng = mid
print(ok)

Submission status: Accepted

Solution code:
import numpy as np

n,k=map(int,input().split())
a=np.array(input().split(),dtype=int)
f=np.array(input().split(),dtype=int)

a=np.sort(a)[::-1]
f=np.sort(f)

ok=10**18
ng=-1

import math
def isOK(val,arr,farr,k):
  return arr.sum()-np.minimum(arr,val//farr).sum()<=k
  
while abs(ok-ng)>1:
  mid=abs(ok+ng)//2
  if isOK(mid,a,f,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()))
f=list(map(int,input().split()))

a=sorted(a)[::-1]
f=sorted(f)

ok=10**18
ng=-1

import math
def isOK(val,arr,farr,k):
  s=0
  for i in range(len(arr)):
    s+=max(math.ceil(a[i]-val/f[i]),0)
  return s<=k
  
while abs(ok-ng)>1:
  mid=abs(ok+ng)//2
  if isOK(mid,a,f,k):
    ok=mid
  else:
    ng=mid
    
print(ok)

Submission status: Accepted

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N,K = MI()
    A=LI()
    B=LI()
    A.sort()
    B.sort(reverse=True)

    def is_ok(x,K):
        for i,a in enumerate(A):
            t = x//B[i]
            K -= max(0,a-t)
        return K>=0

    ok = 10**12+2
    ng = -1
    while ok-ng > 1:
        mid = (ok+ng)//2
        if is_ok(mid,K):
            ok = mid
        else:
            ng = mid
        
    print(ok)
    
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    n, k = list(map(int, input().rstrip('\n').split()))
    a = list(map(int, input().rstrip('\n').split()))
    a.sort()
    f = list(map(int, input().rstrip('\n').split()))
    f.sort(reverse=True)
    cor_v = 10 ** 13
    inc_v = -1
    while cor_v - inc_v > 1:
        bin_v = (cor_v + inc_v) // 2
        cost = 0
        #条件を満たすcostを全検索
        for i in range(n):
            t = a[i] * f[i]
            if t > bin_v:
                cost += (t - bin_v + f[i] - 1) // f[i]
        #costが制約を満たすか
        if cost <= k:
            cor_v = bin_v
        else:
            inc_v = bin_v
    print(cor_v)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import sys
import bisect
import itertools
import collections
import fractions
import heapq
import math
from operator import mul
from functools import reduce
from functools import lru_cache


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    n, k = list(map(int, input().rstrip('\n').split()))
    a = list(map(int, input().rstrip('\n').split()))
    a.sort()
    f = list(map(int, input().rstrip('\n').split()))
    f.sort(reverse=True)
    cor_v = 10 ** 20
    inc_v = -1
    while cor_v - inc_v > 1:
        bin_v = (cor_v + inc_v) // 2
        cost = 0
        #条件を満たすcostを全検索
        for i in range(n):
            t = a[i] * f[i]
            if t > bin_v:
                cost += (t - bin_v + f[i] - 1) // f[i]
        #costが制約を満たすか
        if cost <= k:
            cor_v = bin_v
        else:
            inc_v = bin_v
    print(cor_v)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
n, k = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
f = [int(i) for i in input().split()]
a.sort()
f.sort(reverse=True)

mi = 0
ma = max([i * j for i, j in zip(a, f)])

while mi != ma:
    b = (mi + ma) // 2
    cost = 0
    for i, j in zip(a, f):
        cost += max(0, i - b // j)
    if cost <= k:
        ma = b
    else:
        mi = b + 1
print(mi)

Submission status: Accepted

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

def lower_bound(l, r, ok):
    if ok(l):
        return l
    else:
        return unsafe_lower_bound(l, r, ok)

def unsafe_lower_bound(l, r, ok):
    if l + 1 >= r:
        return r
    m = (l + r) // 2
    if ok(m):
        return lower_bound(l, m, ok)
    else:
        return lower_bound(m, r, ok)

def ok(xs_asc, fs_desc, k, i):
    b = k
    for x, f in zip(xs_asc, fs_desc):
        over = x*f - i
        training = max(0, (over-1)//f+1)
        b -= training
    return b >= 0


def solve(xs, fs, k):
    xs_asc = sorted(xs)
    fs_desc = sorted(fs, reverse=True)
    l = 0
    r = xs_asc[-1] * fs_desc[0]
    return lower_bound(l, r, lambda i: ok(xs_asc, fs_desc, k, i))

print(solve(xs, fs, k))

Submission status: Accepted

Solution code:
import sys


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    n, k = list(map(int, readline().split()))
    a = list(map(int, readline().split()))
    a.sort()
    f = list(map(int, readline().split()))
    f.sort(reverse=True)

    cor_v = 10 ** 13
    inc_v = -1
    while cor_v - inc_v > 1:
        bin_v = (cor_v + inc_v) // 2
        cost = 0
        #条件を満たすcostを全検索
        for i in range(n):
            if a[i] * f[i] >= bin_v:
                cost += ((a[i] * f[i]) - bin_v + f[i] - 1) // f[i]
            if cost > k:
                break
        #costが制約を満たすか
        if cost <= k:
            cor_v = bin_v
        else:
            inc_v = bin_v
    print(cor_v)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import sys


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    n, k = list(map(int, readline().split()))
    a = list(map(int, readline().split()))
    a.sort()
    f = list(map(int, readline().split()))
    f.sort(reverse=True)

    cor_v = 10 ** 20
    inc_v = -1
    while cor_v - inc_v > 1:
        bin_v = (cor_v + inc_v) // 2
        cost = 0
        #条件を満たすcostを全検索
        for i in range(n):
            if a[i] * f[i] >= bin_v:
                cost += ((a[i] * f[i]) - bin_v + f[i] - 1) // f[i]
            if cost > k:
                break
        #costが制約を満たすか
        if cost <= k:
            cor_v = bin_v
        else:
            inc_v = bin_v
    print(cor_v)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import numpy as np

import sys
input = sys.stdin.buffer.readline

N, K = map(int, input().split())
A = np.array(input().split(), np.int64)
F = np.array(input().split(), np.int64)

A.sort()
F.sort()

F= F[::-1]

left = -1
right = (A * F).sum()
while left + 1 < right:
  middle = (left + right) // 2
  right_arr = np.maximum(0, A - middle // F).sum() <= K
  if right_arr:
    right = middle
  else:
    left = middle
print(right)

Submission status: Accepted

Solution code:
import numpy as np

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

a.sort()
f.sort(reverse=True)

a=np.array(a)
f=np.array(f)
s=a.sum()

l,u=-1,f[0]*a[-1]
while l+1<u:
  m=(l+u)//2
  if s-np.minimum(a,m//f).sum()<=k:
    u=m
  else:
    l=m

print(u)

Submission status: Accepted

Solution code:
import numpy as np

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

a.sort()
f.sort(reverse=True)

A=np.array(a)
F=np.array(f)
S=sum(a)

l,u=-1,f[0]*a[-1]
while l+1<u:
  m=(l+u)//2
  s=0
  if S-np.minimum(A,m//F).sum()<=k:
    u=m
  else:
    l=m

print(u)

Submission status: Accepted

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

N,K = map(int,readline().split())
people = np.array(readline().split(),np.int64)
food = np.array(readline().split(),np.int64)
 
people.sort()
food.sort()
food=food[::-1]

#2分探索　Kの値で
_max = max(people)*max(food)
_min = 0

while _max>_min:
  mean = (_max+_min)//2
  # 各人が修行をする回数の配列　負の値もでる
  _K = np.maximum(0,people - mean//food).sum()
  if _K > K:
    _min = mean+1
  else:
    _max = mean
    
print(_max)

Submission status: Accepted

Solution code:

import sys
import numpy as np
readline = sys.stdin.buffer.readline

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

A.sort()
F.sort()
F=F[::-1]

def test(x):
    # 全員がx秒以下に収めるための必要コストがK以下である
    return np.maximum(0,A-x//F).sum() <= K

left = -1 # 不可能目標
right = 10**13 # 可能目標
while left+1 < right:
    mid = (left+right)//2
    if test(mid):
        right = mid
    else:
        left = mid

answer = right
print(answer)
# maspyのやつのほぼコピペ
# 二分探索 時間計算量はO(nlogx)

Submission status: Accepted

Solution code:
import numpy as np
N, K = map(int, input().split())
As = np.sort(list(map(int, input().split())))
Fs = np.sort(list(map(int, input().split())))[::-1]
l  = As*Fs
left = 0
right = max(l)
while right-left>=1:
    mid = left + (right - left)/2
    if np.maximum(As-mid//Fs , 0).sum()<=K:
        right = mid
    else:
        left = mid
print(int(right))

Submission status: Accepted

Solution code:
import numpy as np
import sys

input = sys.stdin.buffer.readline

N,K = map(int,input().split())
A = np.array(input().split(),np.int64)
F = np.array(input().split(),np.int64)

A.sort()
F.sort()
F_ = F[::-1]

m = -1
M = (A*F_).sum()

while (m+1)<M:
    mid = (m+M) //2
    judge = np.maximum(0,A - mid//F_).sum() <= K
    if judge:
        M = mid
    else:
        m = mid
        
print(M)

Submission status: Accepted

Solution code:
import numpy as np

import sys
input = sys.stdin.buffer.readline

n, k = map(int, input().split())
a = np.array(input().split(), np.int64)
f = np.array(input().split(), np.int64)

a.sort()
f.sort()

f_ = f[::-1]

left = -1
right = (a*f_).sum()
while left + 1 < right:
  mid = (left + right) // 2
  r = np.maximum(0, a - mid//f_).sum() <= k
  if r:
    right = mid
  else:
    left = mid
print(right)

Submission status: Accepted

Solution code:
import math
import numpy as np
def yn(a, f, k, x):
  k_yt = np.maximum(np.zeros(a.shape),a - np.floor(np.divide(x, f)))
  k_yt = np.sum(k_yt)
  if k_yt <= k:
    return True
  else:
    return False

n, k = map(int, input().split())
a = list((map(int, input().split())))
f = list((map(int, input().split())))
a.sort()
f.sort(reverse = True)
xo = max([a[i]*f[i] for i in range(n)])
a = np.array(a)
f = np.array(f)
# binary search
if xo == 0:
  print(0)
else:
  l = 0
  r = xo
  m = xo
  while l <= r:
    piv = int((r+l)/2)
    if yn(a, f, k, piv):
      r = piv - 1 
      m = piv
    else:
      l = piv +1
  print(m)

Submission status: Accepted

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

import numpy as np

a = np.array(a)
f = np.array(f)
f_ = f[::-1]

left = -1
right = np.max(a*f_)

while left + 1 < right:
    mid = (left + right)//2
    x = np.maximum(0, a - (mid//f_) ).sum() <= k
    if x:
        right = mid
    else:
        left = mid

print(right)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
AS = list(map(int, input().split()))
FS = list(map(int, input().split()))
AS.sort(); FS.sort(reverse=True)

def isValid(x):
    import math
    trains = 0
    for i in range(N):
        num = AS[i] * FS[i]
        if num <= x: continue
        trains += math.ceil((num - x) / FS[i])
    return trains <= K

def binarySearch(lo, hi):
    if lo >= hi:
        return lo
    mid = lo + (hi - lo) // 2
    if isValid(mid):
        return binarySearch(lo, mid)
    else:
        return binarySearch(mid + 1, hi)
            
print(binarySearch(0, max(AS[i] * FS[i] for i in range(N))))

Submission status: Accepted

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

a.sort(reverse=True)
f.sort(reverse=False)

def isok(mid):
    total = 0
    for i in range(n):
        if a[i] * f[i] <= mid:
            continue
        total += a[i] - mid // f[i]
    return total <= k

ng = -1
ok = a[0] * f[-1] + 1
while abs(ok - ng) > 1:
    mid = (ok + ng) // 2
    if isok(mid):
        ok = mid
    else:
        ng = mid

print(ok)

Submission status: Accepted

Solution code:
import sys
read=sys.stdin.buffer.read
readline=sys.stdin.buffer.readline
readlines=sys.stdin.buffer.readlines

N,K=map(int,readline().split())
A=list(map(int,readline().split()))
F=list(map(int,readline().split()))
#print(N,K)
#print("A:",A)
#print(F)

A.sort()
F.sort(reverse=True)
#print("A:",A)
#print("F:",F)

left=-1
right=N*A[-1]*F[0]
#right=10**3

while left+1<right:
  mid=(left+right)//2
  tmp=0
  for i in range(N):
    tmp+=max(A[i]-mid//F[i],0)
    
  if tmp<=K:
    right=mid
  else:
    left=mid
  #print("mid:",mid,",tmp:",tmp)
#print("left:",left,",mid:",mid,",right:",right)
print(right)

Submission status: Accepted

Solution code:
import sys
read=sys.stdin.buffer.read
readline=sys.stdin.buffer.readline
readlines=sys.stdin.buffer.readlines

N,K=map(int,input().split())
A=list(map(int,input().split()))
F=list(map(int,input().split()))
#print(N,K)
#print("A:",A)
#print(F)

A.sort()
F.sort(reverse=True)
#print("A:",A)
#print("F:",F)

left=-1
right=2*10**17
#right=10**3

while left+1<right:
  mid=(left+right)//2
  tmp=0
  for i in range(N):
    tmp+=max(A[i]-mid//F[i],0)
    
  if tmp<=K:
    right=mid
  else:
    left=mid
  #print("mid:",mid,",tmp:",tmp)
#print("left:",left,",mid:",mid,",right:",right)
print(right)

Submission status: Accepted

Solution code:
import sys
read=sys.stdin.buffer.read
readline=sys.stdin.buffer.readline
readlines=sys.stdin.buffer.readlines

N,K=map(int,input().split())
A=list(map(int,input().split()))
F=list(map(int,input().split()))
#print(N,K)
#print("A:",A)
#print(F)

A.sort()
F.sort(reverse=True)
#print("A:",A)
#print("F:",F)

left=-1
right=10**18
#right=10**3

while left+1<right:
  mid=(left+right)//2
  tmp=0
  for i in range(N):
    tmp+=max(A[i]-mid//F[i],0)
    
  if tmp<=K:
    right=mid
  else:
    left=mid
  #print("mid:",mid,",tmp:",tmp)
#print("left:",left,",mid:",mid,",right:",right)
print(right)

Submission status: Accepted

Solution code:
import sys
read=sys.stdin.buffer.read
readline=sys.stdin.buffer.readline
readlines=sys.stdin.buffer.readlines

N,K=map(int,readline().split())
A=list(map(int,readline().split()))
F=list(map(int,readline().split()))
#print(N,K)
#print("A:",A)
#print(F)

A.sort()
F.sort(reverse=True)
#print("A:",A)
#print("F:",F)

left=-1
right=10**18
#right=10**3

while left+1<right:
  mid=(left+right)//2
  tmp=0
  for i in range(N):
    tmp+=max(A[i]-mid//F[i],0)
    
  if tmp<=K:
    right=mid
  else:
    left=mid
  #print("mid:",mid,",tmp:",tmp)
#print("left:",left,",mid:",mid,",right:",right)
print(right)

Submission status: Accepted

Solution code:
import sys
read=sys.stdin.buffer.read
readline=sys.stdin.buffer.readline
readlines=sys.stdin.buffer.readlines

N,K=map(int,readline().split())
A=list(map(int,readline().split()))
F=list(map(int,readline().split()))
#print(N,K)
#print("A:",A)
#print(F)

A.sort()
F.sort(reverse=True)
#print("A:",A)
#print("F:",F)

left=-1
right=10**18
#right=10**3

while left+1<right:
  mid=(left+right)//2
  tmp=[0]*(N)
  for i in range(N):
    tmp[i]=max(A[i]-mid//F[i],0)
    
  if sum(tmp)<=K:
    right=mid
  else:
    left=mid
  #print("mid:",mid,",tmp:",tmp)
#print("left:",left,",mid:",mid,",right:",right)
print(right)

Submission status: Accepted

Solution code:
# # 整数の入力
# a = int(input())
# # スペース区切りの整数の入力
# b, c = map(int, input().split())
# # 文字列の入力
# s = input()
# a = []
# a = list(map(int, input().split()))
# import math
 
# 解説参照済み
 
n, k = map(int, input().split())
a = []
a = list(map(int, input().split()))
f = []
f = list(map(int, input().split()))
 
a.sort()
f.sort(reverse=True)
ans = 0
 
maxaf = 0
for i in range(n):
    maxaf = max(maxaf, a[i] * f[i])
 
left = 0
right = maxaf
 
while left < right:
    # print(left, right)
    mid = (left + right) // 2
    ktemp = k
    renewleft = False
    for i in range(n):
        if a[i] * f[i] > mid:
            if (a[i] * f[i] - mid + f[i] - 1) // f[i] > ktemp:
                left = mid + 1
                renewleft = True
                break
            else:
                ktemp -= (a[i] * f[i] - mid + f[i] - 1) // f[i]
    if not renewleft:
        right = mid
 
print(left)

Submission status: Accepted

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

a.sort()
f.sort(reverse=True)

pi=[a[i]*f[i] for i in range(n)]

l=-1
r=max(pi)

while l+1<r:
  x=(l+r)//2
  s=sum([max(a[i]-x//f[i],0) for i in range(n)])
  if s<=k:
    r=x
  else:
    l=x
print(r)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
a = [int(c) for c in input().split()]
f = [int(c) for c in input().split()]
a.sort()
f.sort(reverse=True)
def check(n):
  m = K
  for i in range(N):
    m -= max(0, a[i]-n//f[i])
    if m<0:
      return False
  return True
r = 0
l = a[-1]*f[0]
X = (l-r)//2+r
while not (check(X)^check(X+1)) :
  if check(X):
    l = l - (l-r)//2
  else:
    r = (l-r)//2 + r
  X = (l-r)//2+r
  if check(0):
    print(0)
    break
else:
  print(X+1)

Submission status: Accepted

Solution code:
import time
st_time=time.time()

from heapq import heappush, heappop
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations
import sys
import bisect
import string
import math
import random
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
ts=time.time()
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
show_flg=False
#show_flg=True

ans=0
n,k=LI()
a=LI()
f=LI()

a=sorted(a)[::-1]
f=sorted(f)
p=[a[i]*f[i] for i in range(n)]
show(a)
show(f)
show(p)

def check(z):
    c=0
    for i in range(n):
        c+=max(0,a[i]-z//f[i])
    if c<=k:
        rt=True
    else:
        rt=False
    return rt

ng=-1
ok=10**12

while ok-ng>1:
    mid=(ok+ng)//2
    fl=check(mid)
    if fl:
        ok=mid
    else:
        ng=mid
    show(ok,ng,fl)

ans=ok
print(ans)

Submission status: Accepted

Solution code:
NK = input().split(' ')
N = int(NK[0])
K = int(NK[1])
An = sorted(list(map(int,input().split(' '))))
Fn = sorted(list(map(int,input().split(' '))),reverse=True)
An_s = sum(An)

min_time = -1 #middle_time = 0を含めるので -1
max_time = An[N-1] * Fn[0] #最大でかかる時間
x_cadidate = An[N-1] * Fn[0] #xの最小の候補
middle_time = -1
range_n = range(N)
#init_list = [0]*N
while True:
    # max_time+1は max_time=0まで求めるため
    middle_time = (min_time + max_time)//2 #二部探索ように 最大と最小の半分を考える この時 middle_time An[i] * Fn[i]の取りうる最大として考える 
    #new_list = init_list
    sum_ax = 0
    for i in range_n:
        ax = middle_time//Fn[i] # An[i] * Fn[i] = x < middle_time より
        if ax < An[i]:
            sum_ax += ax
        else:
            sum_ax += An[i]
    if  min_time+1 == max_time: #二部探索で全てを探索したら終了 
        break
    elif An_s - sum_ax <= K:
        if x_cadidate > middle_time:
            x_cadidate = middle_time 
        max_time = middle_time   #もう少し middle_timeを減らせる
    else:
        min_time = middle_time   #もう少し middle_timeは大きい

print(x_cadidate)

Submission status: Accepted

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

## 修行前の最短: M
M = max([a*f for a, f in zip(A, F)])

## 積の最小をxにできるか。
## x//f以下である必要がある。
def is_possible(x):
    return sum([max(0, a-x//f) for a, f in zip(A, F)]) <= K

## 2分探索
left = -1
right = M
while left + 1 < right:
    mid = (left + right)//2
    if is_possible(mid):
        right = mid
    else:
        left = mid

print(right)

Submission status: Accepted

Solution code:
N, K = list(map(int, input().split()))
A = sorted(list(map(int, input().split())))
F = sorted(list(map(int, input().split())))[::-1]
B = sum(A)
## 修行前の最短: M
M = max([a*f for a, f in zip(A, F)])

def is_possible(x):
    return B - sum([min(a, x//f) for a, f in zip(A, F)]) <= K

## 2分探索
left = -1
right = M
while left + 1 < right:
    mid = (left + right)//2
    if is_possible(mid):
        right = mid
    else:
        left = mid

print(right)

Submission status: Accepted

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

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

#output
import numpy as np
A = np.array(A)
F = np.array(F)

A = np.sort(A)[::-1]
F = np.sort(F)
B = np.sum(A)
M = max([a*f for a, f in zip(A, F)])

def is_possible(x):
    return B - np.minimum(A, x//F).sum() <= K

left = -1
right = M
while left + 1 < right:
    mid = (left + right)//2
    if is_possible(mid):
        right = mid
    else:
        left = mid

print(right)

Submission status: Accepted

Solution code:
# coding: utf-8
import numpy as np


def solve(*args: str) -> str:
    n, k = map(int, args[0].split())
    A = np.array(sorted(list(map(int, args[1].split()))))
    F = np.array(sorted(list(map(int, args[2].split())), reverse=True))

    right = 1+A[-1]*F[0]
    left = -1

    total = A.sum()
    while left+1 < right:
        mid = (left+right)//2
        if total - np.minimum(A, mid//F).sum() <= k:
            right = mid
        else:
            left = mid

    return str(right)


if __name__ == "__main__":
    print(solve(*(open(0).read().split('\n'))))

Submission status: Accepted

Solution code:
import sys
import math
import bisect
from collections import defaultdict, deque
from heapq import heappush, heappop


def LI(): return [int(x) for x in sys.stdin.readline().split()]


def I(): return int(sys.stdin.readline())


def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res


def IR(n):
    return [I() for i in range(n)]


# A
def A():
    return


# B
def B():
    return


# C
def C():
    n = I()
    for i in range(int(n ** 0.5), 0, -1):
        if n % i == 0:
            print(i + n // i - 2)
            return
    return


# D
def D():
    a, b, x = LI()
    if (x <= a * a * b / 2):
        print(math.degrees(math.atan(a * b * b / x / 2)))
    else:
        print(math.degrees(math.atan(2 * (a * a * b - x) / a ** 3)))
    return


# E
def E():
    n, k = LI()
    a = LI()
    f = LI()
    a.sort()
    f.sort(reverse=True)
    left = 0
    right = 0
    for a_i, f_i in zip(a, f):
        right = max(a_i * f_i, right)
    while (left != right):
        mid = (left + right) >> 1
        score = 0
        for i in range(n):
            if a[i] * f[i] > mid:
                score += a[i] - mid // f[i]
        if score <= k:
            right = mid
        else:
            left = mid + 1
    print(left)
    return


# F
def F():
    return


# Unittest
def resolve():
    E()
    return


# Solve
if __name__ == "__main__":
    E()

Submission status: Accepted

Solution code:
import math

N, K = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
F = [int(x) for x in input().split()]
#%%

A.sort(reverse=True)
F.sort()
max_af = 0
for ind,a in enumerate(A):
    max_af = max(a*F[ind], max_af)

if(sum(A)<=K):
    print(0)
else:
    lower = -1
    higher = 10**12+1

    while(higher-lower>1):
        x = (lower + higher)//2
        
        k = K
        for ind,a in enumerate(A):
            mu = a*F[ind]
            if(mu<=x):
                continue
            else:
                k -= math.ceil((mu-x)/F[ind])
        if(k>=0):
            higher = x
        else:
            lower = x

    print(higher)

Submission status: Accepted

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

A.sort()
F.sort(reverse=True)

sumA = sum(A)
if  K >= sumA:
    print(0)
    exit()

def isok(x):
    k = 0
    for a, f in zip(A, F):
        if a > x//f:
            k += a - (x//f)
            if k > K:
                return False
    return True

ng = -1
ok = 10**12+1

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

Submission status: Accepted

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

a=list(map(int,input().split()))
f=list(map(int,input().split()))
cnt=[0]*n
a.sort()
f.sort(reverse=True)
for i in range(n):
    cnt[i]=a[i]*f[i]
def judge(s):
    tmp=k
    for i in range(n):
        if cnt[i]>s:
            if (cnt[i]-s)%f[i]==0:
                vv=(cnt[i]-s)//f[i]
            else:
                vv=1+(cnt[i]-s)//f[i]
            tmp-=vv
    if tmp<0:
        return False
    return True

left=-1
right=10**18

while left+1<right:
    mid=(left+right)//2
    if judge(mid):
        right=mid
    else:
        left=mid

print(right)

Submission status: Accepted

Solution code:
import numpy as np

import sys
input = sys.stdin.buffer.readline

n, k = map(int, input().split())
a = np.array(input().split(), np.int64)
f = np.array(input().split(), np.int64)

a.sort()
f.sort()

f_ = f[::-1]

left = -1
right = (a*f).sum()
while left + 1 < right:
  mid = (left + right) // 2
  r = np.maximum(0, a - mid//f_).sum() <= k
  if r:
    right = mid
  else:
    left = mid
print(right)