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: Time Limit Exceeded

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

A_sort = sorted(A)
F_sort = sorted(F,reverse=True)

l = -1
r = 10**12

def judge(c):
    s = 0
    for i in range(N):
        s += max(A_sort[i]-c//F_sort[i],0)
    return s <= K

while r-l > 1:
    c = (l+r)//2
    if judge(c):
        r = c
    else:
        l = c
print(max(r,0))

Submission status: Time Limit Exceeded

Solution code:
def main():

    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    F = list(map(int, input().split()))
    A.sort(reverse = True)
    F.sort()

    if K >= sum(A): return 0

    B = [[A[i] * F[i], A[i], F[i]] for i in range(N)]
    l, r = 0, max([A[i]*F[i] for i in range(N)])
    # ans = float('inf')
    while l < r:
        m = (l+r) // 2
        count = 0
        for i in range(N):
            if B[i][0] - m > 0:
                if (B[i][0] - m) % B[i][2] == 0:
                    count += (B[i][0] - m) // B[i][2]
                else:
                    count += (B[i][0] - m) // B[i][2] + 1
        if count <= K:
            if r == m: break
            r = m
        else:
            # ans = min(ans, m)
            if l == m: break
            l = m
        # print(l, r)
    return r



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

Submission status: Time Limit Exceeded

Solution code:
def main():

    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    F = list(map(int, input().split()))
    A.sort(reverse = True)
    F.sort()

    if K >= sum(A): return 0

    B = [[A[i] * F[i], A[i], F[i]] for i in range(N)]
    l, r = 0, max(A) * max(F)
    # ans = float('inf')
    while l < r:
        m = (l+r) // 2
        count = 0
        for i in range(N):
            if B[i][0] - m > 0:
                if (B[i][0] - m) % B[i][2] == 0:
                    count += (B[i][0] - m) // B[i][2]
                else:
                    count += (B[i][0] - m) // B[i][2] + 1
        if count <= K:
            if r == m: break
            r = m
        else:
            # ans = min(ans, m)
            if l == m: break
            l = m
        # print(l, r)
    return r



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

Submission status: Time Limit Exceeded

Solution code:
N,K=map(int, input().split())
A=list(map(int, input().split()))
F=list(map(int, input().split()))
cost = max(sum(A)-K,0)
temp =F[:]
for i in range(cost):
  ind = temp.index(min(temp))
  temp[ind] += F[ind]

print(max([temp[i] - F[i] for i in range(N)]))

Submission status: Time Limit Exceeded

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

a = map(int, input().split())
f = map(int, input().split())

a = sorted(a)
f = sorted(f, reverse=True)

def judge(n):
    s = 0
    for x, y in zip(a, f):
        s += max(0, x - n // y)
    if s <= k:
        return True
    else:
        return False

low = 0
high = a[-1] * f[0]
while high - low > 0:
    mid = (high + low) // 2
    if judge(mid):
        high = mid
    else:
        low = mid + 1
print(high)

Submission status: Time Limit Exceeded

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()]

import sys
import math

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

def cond(score):
    _max = 0
    count = 0
    for i in range(n):
        if a[i] * f[i] <= score:
            continue
        target = (score // f[i])
        count += a[i] - target
        if count > k:
            return False, -1
        _max = max(_max, target * f[i])
    if count <= k:
        return True, _max

def binary_search(start, end, result):
    middle = math.ceil((start + end) / 2)
    if middle == end:
        if result[start]:
            return start
        else:
            return end
    is_ok, score = cond(middle)
    result[middle] = is_ok
    if is_ok:
        return binary_search(start, min(middle, score), result)
    else:
        return binary_search(middle, end, result)

# 0
if sum(a) <= k:
    print(0)
    sys.exit(0)

max_score = 0
for i in range(n):
    max_score = max(max_score, a[i] * f[i])

# max
if k == 0:
    print(max_score)
    sys.exit(0)

# 1 - max
if cond(1)[0]:
    print(1)
    sys.exit(0)

result = {1: False, max_score: True}
print(binary_search(1, max_score, result))

Submission status: Time Limit Exceeded

Solution code:
N,K=map(int, input().split())
A=list(map(int, input().split()))
F=list(map(int, input().split()))
 
cost = max(sum(A)-K,0)
furi =[0]*N
 
temp =F[:]
for i in range(cost):
  ind = temp.index(min(temp))
  temp[ind] += F[ind]
  furi[ind] += 1

print(max([furi[i] * F[i] for i in range(N)]))

Submission status: Time Limit Exceeded

Solution code:
import copy
N,K=map(int, input().split())
A=list(map(int, input().split()))
F=list(map(int, input().split()))
 
cost = max(sum(A)-K,0)
furi =[0]*N
 
temp =copy.copy(F)
for i in range(cost):
  ind = temp.index(min(temp))
  temp[ind] += F[ind]
  furi[ind] += 1
 
print(max([furi[i] * F[i] for i in range(N)]))

Submission status: Time Limit Exceeded

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)

maxaf=a[0]*f[0]
for i in range(n):
	if a[i]*f[i]>maxaf:
		maxaf=a[i]*f[i]

def solve(x):
	total=0
	for i in range(n):
		total+=max(0,a[i]-x//f[i])
	return total<=k

#xの範囲 ngは実現が難しい方
ok=maxaf
ng=-1

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

Submission status: Time Limit Exceeded

Solution code:
import copy
N,K=map(int, input().split())
A=list(map(int, input().split()))
F=list(map(int, input().split()))
 
cost = max(sum(A)-K,0)
furi =[0]*N
 
temp =copy.copy(F)
for i in range(cost):
  ind = temp.index(min(temp))
  temp[ind] += F[ind]
  furi[ind] += 1

print(max([furi[i] * F[i] for i in range(N)]))

Submission status: Time Limit Exceeded

Solution code:
def main():
    n,k,*a=map(int,open(0).read().split())
    a,f=sorted(a[:n]),sorted(a[n:])[::-1]
    ok=10**12
    ng=-1
    while abs(ok-ng)>1:
        mid=(ok+ng)//2
        l=k
        for b,g in zip(a,f):
            if b*g>mid:
                l-=b-mid//g
                if l<0:
                    ng=mid
                    break
        else:ok=mid
    print(ok)
main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    n,k,*a=map(int,open(0).read().split())
    a,f=sorted(a[:n]),sorted(a[n:])[::-1]
    ok=10**12
    ng=-1
    while abs(ok-ng)>1:
        mid=(ok+ng)//2
        l=k
        for b,g in zip(a,f):
            if b*g>mid:
                l-=b-mid//g
            if l<0:
                ng=mid
                break
        else:ok=mid
    print(ok)
main()

Submission status: Time Limit Exceeded

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


def test(x):
    cost = 0
    for i, j in zip(a, f):
        cost += max(0, i - x // j)
    return cost <= k


left = -1
right = a[-1]*f[0]
while left+1 < right:
    mid = (left+right)//2
    if test(mid):
        right = mid
    else:
        left = mid

print(right)

Submission status: Time Limit Exceeded

Solution code:
import sys
def solve(mid):
    l=k
    for b,g in zip(a,f):
        if b*g>mid:
            l-=b-mid//g
            if l<0:return False
    return True
input=sys.stdin.buffer.readline
n,k=map(int,input().split())
a=sorted(map(int,input().split()))[::-1]
f=sorted(map(int,input().split()))
ok=10**12
ng=-1
while abs(ok-ng)>1:
    mid=(ok+ng)//2
    if solve(mid):ok=mid
    else:ng=mid
print(ok)

Submission status: Time Limit Exceeded

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

cost = max(sum(A)-K,0)
furi =[0]*N
 
temp =np.copy(F)
for i in range(cost):
  ind = np.argmin(temp)
  temp[ind] += F[ind]
  furi[ind] += 1
  
print(max(furi*F))

Submission status: Time Limit Exceeded

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

A_n = np.array(A)
F_n = np.array(F)
A_sort = np.sort(A_n)
F_sort = np.sort(F_n)[::-1]
 
for j in range(K):

    np_list = A_sort*F_sort
    max_index = np_list.argmax()
    if max(A_sort) == 0:
        break
    else:
        A_sort[max_index] -= 1
    
ans = 0

print(max(A_sort*F_sort))

Submission status: Time Limit Exceeded

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


def test(x):
    cost = 0
    for i, j in zip(a, f):
        cost += max(0, i - x // j)
    return cost <= k


left = -1
right = 10**12
while left+1 < right:
    mid = (left+right)//2
    if test(mid):
        right = mid
    else:
        left = mid

print(right)

Submission status: Time Limit Exceeded

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)
high = 10**13
low = -1

# 全員が目指す目標値midを作って達成可能かどうかを調べる
while low+1 < high:
    mid = (low + high) // 2
    a_sub_sum = 0
    for ai, fi in zip(a, f):
        a_sub_sum += ai - min(ai, mid // fi)
    if a_sub_sum <= k: # 達成可能
        high = mid
    else:
        low = mid
print(high)

Submission status: Time Limit Exceeded

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


def test(x):
    cost = 0
    for i in range(n):
        cost += max(0, a[i] - x // f[i])
    return cost <= k


left = -1
right = 10**12
while left+1 < right:
    mid = (left+right)//2
    if test(mid):
        right = mid
    else:
        left = mid

print(right)

Submission status: Time Limit Exceeded

Solution code:
from heapq import *
def abc144c():
  n,k=map(int,input().split())
  a=sorted(list(map(int,input().split())))
  f=sorted(list(map(int,input().split())))[::-1]
  q=[] 
  for i,j in zip(a,f):
    heappush(q,(-i*j,j))
  for i in range(k):
    tmp,key=heappop(q)
    heappush(q,(tmp+key,key))
  ans,key=heappop(q)
  print(max(-ans,0))
abc144c()

Submission status: Time Limit Exceeded

Solution code:
N,K = map(int, input().strip().split(' '))
A = sorted(list(map(int, input().strip().split(' '))), reverse=True)
F = sorted(list(map(int, input().strip().split(' '))))
if sum(A) <= K:
  print(0)
  exit()

ng = 0
ok = max([a*f for a,f in zip(A,F)])
while True:
  if ok-ng == 1: break
  m = int((ng+ok)/2)
  now_cost = 0
  for a,f in zip(A,F):
    while a*f > m:
      a -= 1
      now_cost += 1
  if now_cost <= K:
    ok = m
  else:
    ng = m
    
print(ok)

Submission status: Time Limit Exceeded

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)
a_sum = sum(a)
high = 10**13
low = -1

# 全員が目指す目標値midを作って達成可能かどうかを調べる
while low+1 < high:
    mid = (low + high) // 2
    ary = []
    for ai, fi in zip(a, f):
        ary.append(ai - min(ai, mid // fi))
    if sum(ary) <= k: # 達成可能
        high = mid
    else:
        low = mid
print(high)

Submission status: Time Limit Exceeded

Solution code:
def main():
    import bisect
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    f = list(map(int, input().split()))
    a.sort()
    f.sort(reverse = True)
    d = [[f[i]*a[i], f[i], a[i]] for i in range(n)]
    for i in range(k):
        if d[d.index(max(d))][2] > 0:
            d[d.index(max(d))][2] -= 1
            d[d.index(max(d))][0] -= d[d.index(max(d))][1]
        else:
            break
    print(d[d.index(max(d))][0])
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import math

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

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

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

def check(x):
  k = K
  for i in range(N):
    k -= max(0,math.ceil((A[i]*F[i]-x)/F[i]))

  return k >= 0



left = 0
right = 10**12

if check(left):
  print(0)
  exit()

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


print(right)

Submission status: Time Limit Exceeded

Solution code:
import bisect
n, k = map(int, input().split())
a = list(map(int, input().split()))
f = list(map(int, input().split()))
a.sort()
f.sort(reverse = True)
d = [[f[i]*a[i], f[i], a[i]] for i in range(n)]
d.sort(reverse = True)
for i in range(k):
    if d[0][2] > 0:
        d[0][0] -= d[0][1]
        d[0][2] -= 1
        d.sort(reverse = True)
    else:
        break
print(d[0][0])

Submission status: Time Limit Exceeded

Solution code:
# E - Gluttony

import numpy as np

# np.arrayに変換する場合、sortedを使うよりnp.sortを使う方が速い(使わないとTLE)
N, K = map(int, input().split())
A = np.sort(np.array((list(map(int, input().split())))))
F = np.sort(np.array((list(map(int, input().split())))))[::-1]

lower = 0
upper = A[-1] * F[0]

# 達成可能な最高成績を二分探索する
while lower <= upper:
    result = (lower + upper) // 2
    if sum(np.clip(A - result//F, 0, None)) <= K: # resultを達成可能なAと実際のAの差異の総和が必要な修行コスト
        ans = result
        upper = result - 1
    else:
        lower = result + 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# E - Gluttony

import numpy as np

N, K = map(int, input().split())
A = np.array(sorted(list(map(int, input().split()))))
F = np.array(sorted(list(map(int, input().split())), reverse = True))

lower = 0
upper = A[-1] * F[0]

# 達成可能な最高成績を二分探索する
while lower <= upper:
    result = (lower + upper) // 2
    if sum(np.clip(A - result//F, 0, None)) <= K: # resultを達成可能なAと実際のAの差異の総和が必要な修行コスト
        ans = result
        upper = result - 1
    else:
        lower = result + 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
A = list( map(int, input().split()))
F = list( map(int, input().split())) 
A = sorted(A)
F = sorted(F, reverse = True)

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

ok = max(A)*max(F)
ng = 0

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

Submission status: Time Limit Exceeded

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)
a_sum = sum(a)
high = max(x*y for x, y in zip(a, f))
low = -1

# 全員が目指す目標値midを作って達成可能かどうかを調べる
while low+1 < high:
    mid = (low + high) // 2
    ary = []
    for ai, fi in zip(a, f):
        ary.append(ai - min(ai, mid // fi))
    if sum(ary) <= k: # 達成可能
        high = mid
    else:
        low = mid
print(high)

Submission status: Time Limit Exceeded

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

a = map(int, input().split())
f = map(int, input().split())

a = sorted(a)
f = sorted(f, reverse=True)

score = sorted(((x * y, x, y) for (x, y) in zip(a, f)))
for _ in range(k):
    p, x, y = score.pop()
    if x > 0:
        x -= 1
    bisect.insort(score, (x * y, x, y))

p, _, _ = score.pop()
print(p)

Submission status: Time Limit Exceeded

Solution code:
def main():
    n,k,*a=map(int,open(0).read().split())
    a,f=sorted(a[:n])[::-1],sorted(a[n:])
    ok=10**12
    ng=-1
    while abs(ok-ng)>1:
        mid=(ok+ng)//2
        l=k
        for i in range(n):
            if a[i]*f[i]>mid:
                l-=a[i]-mid//f[i]
        if l<0:ng=mid
        else:ok=mid
    print(ok)
main()

Submission status: Time Limit Exceeded

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

a = list(map(int, input().split()))
f = list(map(int, input().split()))

a = sorted(a)
f = sorted(f, reverse=True)

score = sorted(((x * y, x, y) for (x, y) in zip(a, f)))
for _ in range(k):
    p, x, y = score.pop()
    if x > 0:
        x -= 1
    bisect.insort(score, (x * y, x, y))

p, _, _ = score.pop()
print(p)

Submission status: Time Limit Exceeded

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

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

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


MIN=0
MAX=max(A)*max(F)

while MIN!=MAX:
    mid=(MIN+MAX)//2
    score=0

    for i in range(N):
        if A[i]*F[i]>mid:
            score+=A[i]-mid//F[i]

    if score<=K:
        MAX=mid
    else:
        MIN=mid+1

print(MIN)

Submission status: Time Limit Exceeded

Solution code:
import sys
def solve(mid):
    l=k
    for b,g in zip(a,f):
        if b*g>mid:
            l-=b-mid//g
    if l<0:return False
    return True
input=sys.stdin.buffer.readline
n,k=map(int,input().split())
a=sorted(map(int,input().split()))[::-1]
f=sorted(map(int,input().split()))
ok=10**12
ng=-1
while ok-ng>1:
    mid=(ok+ng)//2
    if solve(mid):
        ok=mid
    else:
        ng=mid
print(ok)

Submission status: Time Limit Exceeded

Solution code:
import bisect

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

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

if sum(A) <= K:
    ans = 0
else:
    AF = [A[i] * F[i] for i in range(N)]
    high = max(AF)
    low = 0
    mid = (high + low) // 2
    while low < mid < high:
        Ki = K
        able = True
        for i in range(N):
            if AF[i] > mid:
                Ki -= A[i] - mid // F[i]
                if Ki < 0:
                    able = False
                    break
        if able:
            high = mid
        else:
            low = mid
        mid = (high + low) // 2
    ans = high

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def solve(mid):
    l=k
    for b,g in zip(a,f):
        if b*g>mid:
            l-=b-mid//g
    if l<0:return False
    return True
n,k,*a=map(int,open(0).read().split())
a,f=sorted(a[:n])[::-1],sorted(a[n:])
ok=10**12
ng=-1
while abs(ok-ng)>1:
    mid=(ok+ng)//2
    if solve(mid):
        ok=mid
    else:
        ng=mid
print(ok)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import Counter, deque, defaultdict
from math import factorial
from fractions import Fraction
import heapq, bisect
import math
import itertools
sys.setrecursionlimit(10 ** 5 + 10)
INF = 10**15 +5
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()))

n, k = MAP()
a = LIST()
f = LIST()
a = sorted(a, reverse = True)
f = sorted(f)
heap = []
heapq.heapify(heap)
for i in range(n):
    heapq.heappush(heap, (-1*f[i]*a[i], f[i]))

for i in range(k):
    if len(heap) > 0:
        dot, ff = heapq.heappop(heap)
        dot += ff
        if dot != 0:
            heapq.heappush(heap, (dot, ff))

if len(heap) > 0:
    print(heapq.heappop(heap)[0] * -1)
else:
    print(0)

Submission status: Time Limit Exceeded

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, atan, degrees
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect
import heapq

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()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

def main():
	N, K = MAP()
	A = LIST()
	F = LIST()

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

	time = [A[i]*F[i] for i in range(N)]
	# print(F)
	# print(time)

	sum_A = sum(A)

	def is_ok(x):  # 時間をx以下にできるか？
		tmp = [0]*N
		for i in range(N):
			tmp[i] = min(A[i], x//F[i])
		return sum_A - sum(tmp) <= K

	min_ = -1
	max_ = 10**18
	while min_ + 1 != max_:
		search = (min_+max_)//2
		# print(min_, max_, search)
		if is_ok(search):
			max_ = search
		else:
			min_ = search

	print(max_)


if __name__ == "__main__":
	main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    N, K, *I = map(int, open(0).read().split())
    A, F = I[:N], I[N:]

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

    ng, ok = -1, 10 ** 12
    while abs(ok - ng) > 1:
        mid = (ok + ng) // 2
        if sum(max(0, a - mid // f) for a, f in zip(A, F)) <= K:
            ok = mid
        else:
            ng = mid

    print(ok)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
a=[int(j) for j in input().split()]
f=[int(j) for j in input().split()]
a.sort()
f.sort()
f.reverse()
if k>=sum(a):
    print(0)
    exit()

ans=[]
a.sort()
for i in range(n):
    ans.append([a[i]*f[i],a[i]])
ans.sort()
ans.reverse()

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

left=0
right=ans[0][0]
while right-left>1:
    mid=(left+right)//2
    if fun(mid):
        right=mid   #ここがleftならansもleft。
    else:
        left=mid

print(right)

Submission status: Time Limit Exceeded

Solution code:
def main():
    n,k,*a=map(int,open(0).read().split())
    *z,=zip(sorted(a[:n])[::-1],sorted(a[n:]))
    ok=10**12
    ng=-1
    while ok-ng>1:
        mid=(ok+ng)//2
        l=k
        for b,g in z:
            if b*g>mid:
                l-=b-mid//g
        if l<0:ng=mid
        else:ok=mid
    print(ok)
main()