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 sys
input = sys.stdin.buffer.readline

def main():
    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 func(x):
        count = 0
        for co,ha in zip(a,f):
            tr = x//ha
            if co <= tr:
                continue
            count += co-tr
        if K < count:
            return True
        else:
            return False
    l,r = -1,a[-1]*f[0]+1
    while r-l > 1:
        mid = (l+r)//2
        if func(mid):
            l = mid
        else:
            r = mid
            
    print(r)
    
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

def main():
    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 func(x):
        count = 0
        for co,ha in zip(a,f):
            tr = max(0,co - mid//ha)
            count += tr
        if K < count:
            return True
        else:
            return False
    l,r = -1,a[-1]*f[0]+1
    while r-l > 1:
        mid = (l+r)//2
        if func(mid):
            l = mid
        else:
            r = mid
            
    print(r)
    
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

def main():
    N,K = map(int,input().split())
    a = list(map(int,input().split()))
    f = list(map(int,input().split()))
    a.sort()
    f.sort(reverse = True)
    l,r = -1,a[-1]*f[0]+1
    while r-l > 1:
        mid = (l+r)//2
        count = 0
        for co,ha in zip(a,f):
            tr = max(0,co - mid//ha)
            count += tr
        if K < count:
            l = mid
        else:
            r = mid
            
    print(r)
    
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

def main():
    N,K = map(int,input().split())
    a = list(map(int,input().split()))
    f = list(map(int,input().split()))
    a.sort()
    f.sort(reverse = True)
    l,r = -1,a[-1]*f[0]+1
    while r-l > 1:
        mid = (l+r)//2
        count = 0
        for i in range(N):
            tr = max(0,a[i] - mid//f[i])
            count += tr
        if K < count:
            l = mid
        else:
            r = mid
            
    print(r)
    
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
*A, = map(int, input().split())
*F, = map(int, input().split())
A.sort()
F.sort(reverse=True)

def f(x):
    ans = 0
    for i,j in zip(A, F):
        ans += (i*j-x+j-1)//j if i*j-x>=0 else 0
    return ans<=K

l, r = -1, 10**18+1
while r-l>1:
    mid = (r+l)//2
    if f(mid):
        r = mid
    else:
        l = mid

print(r)

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)


def C(x):
    train = 0
    for a, f in zip(A, F):
        train += max(0, a - x // f)

    return train <= K


left = -1
right = 10 ** 12 + 1
while right > left + 1:
    mid = (right + left) // 2
    if C(mid):  # 食べきれる場合
        right = mid
    else:
        left = mid

ans = right
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import heapq


def main():
    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 = sorted(A)
    F = reversed(sorted(F))

    cost_list = []
    for a, f in zip(A, F):
        cost_list.append([-a*f, a, f])

    heapq.heapify(cost_list)

    for _ in range(K):
        max_cost = heapq.heappop(cost_list)
        max_cost[1] -= 1
        max_cost[0] = -max_cost[1]*max_cost[2]
        heapq.heappush(cost_list, max_cost)

    print(-cost_list[0][0])


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

import numpy as np

def main():
  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))
  def is_time(x):
    c = 0
    for i in range(n):
      c = np.maximum(A - x//F, 0).sum()
    if c <= k:
      return True
    return False
  ng = -1
  ok = max(A*F)
  while ok - ng > 1:
    m = (ng + ok)//2
    if is_time(m):
      ok = m
    else:
      ng = m
  print(ok)
  
if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

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

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))
def is_time(x):
  c = 0
  for i in range(n):
    c = np.maximum(A - x//F, 0).sum()
  if c <= k:
    return True
  return False
ng = -1
ok = max(A*F)
while ok - ng > 1:
  m = (ng + ok)//2
  if is_time(m):
    ok = m
  else:
    ng = m
print(ok)

Submission status: Time Limit Exceeded

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

from heapq import heappush, heappop

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

A = sorted(A)
F = sorted(F)[::-1]

h = []
for i in range(N):
  a, f = A[i], F[i]
  heappush(h, (- a * f, a, f))
  
while K > 0:
  x, y, z = heappop(h)
  if x == 0:
    break
  else:
    heappush(h, (- (y - 1) * z, (y - 1), z))
    K -= 1
    
x, y, z = heappop(h)
print(-x)

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)


# にぶたん := N人のメンバーそれぞれが完食にかかる時間のうち最大値をxに以下にできるか？
ok, ng = 10 ** 12 + 1, -1
while ok - ng > 1:
    x = (ok + ng) // 2

    need_training = 0
    for a, f in zip(A, F):
        need_training += max(0, a - x // f)

        if need_training > K:
            ng = x
            break
    else:
        ok = x

print(ok)

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)


# にぶたん := N人のメンバーそれぞれが完食にかかる時間のうち最大値をxに以下にできるか？
ok, ng = 10 ** 18, -1
while ok - ng > 1:
    x = (ok + ng) // 2

    need_training = 0
    for a, f in zip(A, F):
        need_training += max(0, a - x // f)

        if need_training > K:
            ng = x
            break
    else:
        ok = x

print(ok)

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)


# にぶたん := N人のメンバーそれぞれが完食にかかる時間のうち最大値をxに以下にできるか？
ok, ng = 10 ** 18, -1
while ok - ng > 1:
    x = (ok + ng) // 2

    need_training = 0
    for a, f in zip(A, F):
        need_training += max(0, a - x // f)

    if need_training <= K:
        ok = x
    else:
        ng = x

print(ok)

Submission status: Time Limit Exceeded

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

# もし修行により消化コストが全て0になる場合
if sum(a_list) <= k:
    print(0)
    exit()

# 更新メソッド
def update_cost(max_idx, result_cost, a_list, f_list):

    result_cost[max_idx] = a_list[max_idx] * f_list[max_idx]

    if max_idx == 0:
        pass
    else:
        result_cost[max_idx-1] = a_list[max_idx-1] * f_list[max_idx-1]

    return result_cost

# ソート
a_list.sort()
f_list.sort(reverse=True)

# コストリストinit
result_cost = [a_list[idx] * f_list[idx] for idx in range(len(a_list))]


# 修行する
while k > 0:
    # 現状で最もコストが大きいものについて考える
    max_idx = result_cost.index(max(result_cost))

    # 修行実行
    a_list[max_idx] -= 1
    a_list.sort()

    # コストリスト更新
    result_cost = update_cost(max_idx, result_cost, a_list, f_list)

    # 修行数減らす
    k -= 1

print(max(result_cost))

Submission status: Time Limit Exceeded

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

# もし修行により消化コストが全て0になる場合
if sum(a_list) <= k:
    print(0)
    exit()

# 更新メソッド
def update_cost():
    min_cost = []
    for i in range(len(a_list)):
        min_cost.append(a_list[i] * f_list[i])
    return min_cost

# ソート
a_list.sort()
f_list.sort(reverse=True)

# コストリストinit
result_cost = update_cost()


# 修行する
while k > 0:
    # 現状で最もコストが大きいものについて考える
    max_idx = result_cost.index(max(result_cost))

    # 修行実行
    a_list[max_idx] -= 1
    a_list.sort()

    # コストリスト更新
    result_cost = update_cost()

    # 修行数減らす
    k -= 1

print(max(result_cost))

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush, heappushpop, heappop

N, K = map(int, input().split())
A = list(map(lambda x: -int(x), input().split()))
F = list(map(int, input().split()))
A.sort()
F.sort()


hq = []
for a, f in zip(A, F):
    heappush(hq, (a * f, f))

c, f = heappop(hq)
while K > 0:
    c += f
    K -= 1
    c, f = heappushpop(hq, (c, f))

print(-c)

Submission status: Time Limit Exceeded

Solution code:
import sys
import bisect
import math
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)

B = [(A[i]*F[i], F[i]) for i in range(N)]
B.sort(reverse=True)
L = 0
R = B[0][0]
if sum(A) <= K:
    print(0)
    exit(0)
while(1):
    ans = (L+R) // 2
    flag = True
    tmp = 0
    for i in range(N):
        tmp += math.ceil(max(B[i][0] - ans, 0) / B[i][1])
        if tmp > K:
            flag = False
            break
    if flag:
        R = ans
    else:
        L = ans
    if L == R or L+1 == R:
        print(R)
        break

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

def solve(A, F, K):
    lo = 0
    hi = 10 ** 12
    while lo < hi:
        mid = (lo + hi) // 2
        total_train = 0
        for i in range(A.shape[0]):
            need = A[i] - mid // F[i]
            total_train += need if need > 0 else 0
        if total_train <= K:
            hi = mid
        else:
            lo = mid + 1
    return lo

stdin = np.fromstring(open(0).read(), dtype=np.int64, sep=' ')
N, K = stdin[:2]
A = stdin[2: 2 + N]
F = stdin[2 + N:]
print(solve(np.sort(A)[::-1], np.sort(F), K))

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)
l = -1
r = 10 ** 13
while r - l > 1:
  m = (l + r) // 2
  if sum([(a - m // f) if a * f > m else 0 for a, f in zip(A, F)]) <= k:
    r = m
  else:
    l = m
    
print(r)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N, K = map(int,input().split())
A = np.sort(list(map(int,input().split())))
F = np.sort(list(map(int,input().split())))[::-1]
mul = A*F
if K >= sum(A)*N:
    print(0)
    exit()

ma = 2**40
mi = 0
while 1:
    tgt = (ma + mi)//2
    num = 0
    for m,f in zip(mul,F):
        tmp = np.ceil((m-tgt)/f)
        if tmp < 0:
            continue
        num += tmp
    if ma == mi:
        print(ma)
        exit()
    if num <= K:
        ma = mi + (ma - mi)//2
    else:
        mi = mi + (ma - mi)//2+1

Submission status: Time Limit Exceeded

Solution code:
def is_ok(x, A, F):
    trainings = 0
    for i in range(N):
        t = A[i] - x // F[i]
        if t > 0:
            trainings += t
    return trainings <= K


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

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

ng = -1
ok = A[-1] * F[0]
while ok - ng > 1:
    m = ng + (ok - ng) // 2
    if is_ok(m, A, F):
        ok = m
    else:
        ng = m
print(ok)

Submission status: Time Limit Exceeded

Solution code:
def is_ok(x, A, F):
    result = 0
    for i in range(N):
        a = A[i]
        t = x // F[i]
        if t < a:
            result += a - t
    return result <= K


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

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

ng = -1
ok = A[-1] * F[0]
while ok - ng > 1:
    m = ng + (ok - ng) // 2
    if is_ok(m, A, F):
        ok = m
    else:
        ng = m
print(ok)

Submission status: Time Limit Exceeded

Solution code:
def is_ok(x):
    result = 0
    for i in range(N):
        a = A[i]
        t = x // F[i]
        if t < a:
            result += a - t
    return result <= K


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

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

ng = -1
ok = A[-1] * F[0]
while ok - ng > 1:
    m = ng + (ok - ng) // 2
    if is_ok(m):
        ok = m
    else:
        ng = m
print(ok)

Submission status: Time Limit Exceeded

Solution code:
from math import ceil
n,k=map(int,input().split())
a=sorted(list(map(int,input().split())))
f=sorted(list(map(int,input().split())),reverse=True)
l=[]
for i in range(n):
  l.append([f[i]*a[i],a[i],f[i]])
l.sort()
ng=-1
ok=l[n-1][0]
while ok-ng>1:
  mid=(ok+ng)//2
  cnt=0
  for i in range(n):
    if l[i][0]>mid:
      cnt+=ceil((l[i][0]-mid)/l[i][2])
  if cnt<=k:
    ok=mid
  else:
    ng=mid
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)
def ok(p):
  result = 0
  for i in range(n):
    result += max(a[i]-p//f[i],0)
  if result <= k:
    return True
  return False

L = 0
U = a[-1]*f[0]
while U-L >= 1:
  M = (U+L)//2
  if ok(M):
    U = M
  else:
    L = M+1
    
print(U)

Submission status: Time Limit Exceeded

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

def ok(N):
    sums=0
    for i in range(n):
        sums+=max(0,a[i]-N//b[i])
    if sums<=k:
        return True
    else:
        return False
    
import math

left=0
right=a[0]*b[-1]
P=0
for i in range(41):
    if 2**i<=right<2**(i+1):
        P=i+1
        break

for _ in range(P):
    if ok(math.floor((left+right)/2)):
      left=left
      right=(left+right)/2
    elif not ok(math.floor((left+right)/2)):
      left=(left+right)/2
      right=right
print(math.floor(right))

Submission status: Time Limit Exceeded

Solution code:
import sys
import math

input=sys.stdin.readline

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

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

def ok(N):
    sums=0
    for i in range(n):
        sums+=max(0,a[i]-N//b[i])
    if sums<=k:
        return True
    else:
        return False
    


left=0
right=10**12

for _ in range(40):
    if ok(math.floor((left+right)/2)):
      left=left
      right=(left+right)/2
    elif not ok(math.floor((left+right)/2)):
      left=(left+right)/2
      right=right
print(math.floor(right))

Submission status: Time Limit Exceeded

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

def ok(N):
    sums=0
    for i in range(n):
        sums+=max(0,a[i]-N//b[i])
    if sums<=k:
        return True
    else:
        return False
    
import math

left=0
right=10**12
for _ in range(40):
    if ok(math.floor((left+right)/2)):
      left=left
      right=(left+right)/2
    elif not ok(math.floor((left+right)/2)):
      left=(left+right)/2
      right=right
print(math.floor(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()
suma = sum(A)
u = 10**12
d = 0
for i in range(50):
    x = (u + d)//2
    s = 0
    for i in range(N):
        f = F[i]
        j = -(i+1)
        a = A[j]
        b = x // f
        s += max(0,a-b)
    if s <= K:
        u = x
    else:
        d = x
print(u)

Submission status: Time Limit Exceeded

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

def main():
    N,K = map(int,input().split())
    A = list(map(int,input().split()))
    F = list(map(int,input().split()))
    if sum(A) <= K:
        print(0)

    else:
        A.sort()
        F.sort(reverse=True)
    
        score = []
        for i in range(N):
            score.append((-A[i]*F[i],F[i]))
        heapq.heapify(score)
        for i in range(K):
            cost,diff = heapq.heappop(score)
            cost += diff
            heapq.heappush(score,(cost,diff))
        
        mscore,diff = heapq.heappop(score)
        print(-mscore)
    
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def ints():
  return [int(x) for x in input().split()]
def ii():
  return int(input())

import math

N, K = ints()
A = list(sorted(ints()))
F = list(reversed(sorted(ints())))
AF = [A[i]*F[i] for i in range(N)]

afmax = max(AF)

def can(max_af):
  k = K
  for i in range(N):
    af = AF[i]
    if af>max_af:
      max_ai = max_af // F[i]
      k -= A[i]-max_ai
      if k<0:
        return False
  return k>=0

l = -1
r = afmax
while r-l>1:
  m = (l+r)//2
  if can(m):
    r = m
  else:
    l = m
print(r)

Submission status: Time Limit Exceeded

Solution code:
def ints():
  return [int(x) for x in input().split()]
def ii():
  return int(input())

import math

N, K = ints()
A = list(sorted(ints()))
F = list(reversed(sorted(ints())))

afmax = max([a*f for a in A for f in F])

def binsearch(cant_lower, can_upper):
  if cant_lower+1==can_upper:
    return can_upper

  m = (cant_lower + can_upper)//2

  if can(m):
    return binsearch(cant_lower, m)
  else:
    return binsearch(m, can_upper)

def can(seiseki):
  k = K
  for i in range(N):
    if A[i]*F[i]>seiseki:
      k -= math.ceil((A[i]*F[i]-seiseki)/F[i])
  return k>=0

w = binsearch(-1, afmax)
print(w)

Submission status: Time Limit Exceeded

Solution code:
import heapq

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

A.sort()
F.sort(reverse=True)
#print(N, K, A, F)
hq = []
for i in range(N):
    a = A[i]
    f = F[i]
    heapq.heappush(hq, (-a * f, a, f))

for i in range(K):
    v = heapq.heappop(hq)
    a = v[1]
    f = v[2]
    if a == 0:
        break
    a -= 1
    heapq.heappush(hq, (-a*f, a, f))
ans = heapq.heappop(hq)
print(-ans[0])

Submission status: Time Limit Exceeded

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

    a=0
    b=10**12+10
    while a+1 < b:
        med = (a+b)//2
        cnt = 0
        for i in range(n):
            cnt += max(aa[i]-med//f[i], 0)
        if cnt > k:
            a = med+1
        else:
            b = med
    if a == b:
        print(a)
    else:
        cnt = 0
        for i in range(n):
            cnt += max(aa[i]-a//f[i], 0)
        if cnt > k:
            print(b)
        else:
            print(a)


main()

Submission status: Time Limit Exceeded

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

    def b_search(a, b):
        while a+1 < b:
            med = (a+b)//2
            cnt = 0
            for i in range(n):
                cnt += max(aa[i]-med//f[i], 0)
            if cnt > k:
                a = med+1
            else:
                b = med
        if a == b:
            return a
        else:
            cnt = 0
            for i in range(n):
                cnt += max(aa[i]-a//f[i], 0)
            if cnt > k:
                return b
            else:
                return a

    print(b_search(0, 10**12+10))


main()

Submission status: Time Limit Exceeded

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

    def b_search(a, b, value):
        while a+1 < b:
            med = (a+b)//2
            if value(med):
                b = med
            else:
                a = med+1
        if a == b:
            return a
        else:
            if value(a):
                return a
            else:
                return b

    def count(val):
        cnt = 0
        for i in range(n):
            cnt += max(a[i]-val//f[i], 0)
        if cnt > k:
            return False
        else:
            return True

    print(b_search(0, 10**12+10, count))


main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import heapq
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, m=DVSR): return pow(x, m - 2, m)
def DIV(x, y, m=DVSR): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(input())
def FLIST(n):
    res = [1]
    for i in range(1, n+1): res.append(res[i-1]*i%DVSR)
    return res

N,K=LI()
As=LI()
As.sort()
Fs=LI()
Fs.sort(reverse=True)

HQ=[]

for i in range(N):
    heapq.heappush(HQ, (-As[i]*Fs[i], As[i], Fs[i]))

# print(HQ)
while K:
    score,A,F=heapq.heappop(HQ)
    if HQ:
        score2,A2,F2=HQ[0]
        diff = min((score2 - score) // F + 1, K)

        heapq.heappush(HQ, (-(A-diff)*F , A-diff, F))
        K = K - diff
    else:
        print(max(A-K,0)*F)
        exit()

ans, _, _ =heapq.heappop(HQ)
print(-ans)

Submission status: Time Limit Exceeded

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

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

def score(x):
    syugyo = 0
    for A,F in zip(a,f):
        sup = x//F
        if sup < A:
            syugyo += A-sup
    if syugyo <= k:
        return True
    else:
        return False


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

Submission status: Time Limit Exceeded

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

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

def score(x):
    syugyo = 0
    for A,F in zip(a,f):
        syugyo += max(A-x//F,0)
    if syugyo <= k:
        return True
    else:
        return False


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

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)

def score(x):
    syugyo = 0
    for A,F in zip(a,f):
        sup = int(x/F)
        if sup < A:
            syugyo += A-sup
    if syugyo <= k:
        return True
    return False


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

Submission status: Time Limit Exceeded

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

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

def score(x):
    syugyo = 0
    for A,F in zip(a,f):
        sup = int(x/F)
        if sup < A:
            syugyo += A-sup
    if syugyo <= k:
        return True
    return False


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

Submission status: Time Limit Exceeded

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

# aとfの組み合わせはソートして逆向きが最適
# 帰納法で示す

# チームの成績x→単に成績x,メンバーiの成績→xi

# 0<=x<=a[-1]*f[0]な整数xがあったら
# 成績x以下にすることはできるか？という命題を考える

# gi=int(x/fi)は食べ物iで成績xiを出せる最大値
# 　aiがgiを超えてしまうと成績xi以下は修行しないと出せない
# 　ai<=giならその人の成績はxi以下になる
# なのでmax(ai-gi,0)は成績xi以下であるために必要な修行の回数

# よってsum=Σmax(ai-gi,0)は成績x以下を達成するのに、必要なチーム全体の総修行回数
# したってsum<=Kなら成績x以下にすることができる

# 各整数について命題はFalseかTrueを返す
# その順番は1から順にF...FT...Tとなる
# この一番左のTの整数xが求めたい最小値：チームの成績xの最小値

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

def score(x):
    syugyo = 0
    for A,F in zip(a,f):
        syugyo += max(A-int(x/F),0)
    if syugyo <= k:
        return True
    return False


left = 0
right = a[-1]*f[0]+1
while left < right-1:
    mid = (left+right)//2
    if score(mid):
        right = mid
    else:
        left = mid
print(left+1 if left != 0 else 0)
    
# 計算量は 1+2logN + N*log(2)N <= N*logN < 3.6 * 10^6 
# ぎりぎりセーフ？

Submission status: Time Limit Exceeded

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

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

def score(x):
    syugyo = 0
    for A,F in zip(a,f):
        syugyo += max(A-int(x/F),0)
    if syugyo <= k:
        return True
    else:
        return False

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

Submission status: Time Limit Exceeded

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

# aとfの組み合わせはソートして逆向きが最適
# 帰納法で示す

# チームの成績x→単に成績x,メンバーiの成績→xi

# 0<=x<=a[-1]*f[0]な整数xがあったら
# 成績x以下にすることはできるか？という命題を考える

# gi=int(x/fi)は食べ物iで成績xiを出せる最大値
# 　aiがgiを超えてしまうと成績xi以下は修行しないと出せない
# 　ai<=giならその人の成績はxi以下になる
# なのでmax(ai-gi,0)は成績xi以下であるために必要な修行の回数

# よってsum=Σmax(ai-gi,0)は成績x以下を達成するのに、必要なチーム全体の総修行回数
# したってsum<=Kなら成績x以下にすることができる

# 各整数について命題はFalseかTrueを返す
# その順番は1から順にF...FT...Tとなる
# この一番左のTの整数xが求めたい最小値：チームの成績xの最小値

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

def score(x):
    syugyo = 0
    for A,F in zip(a,f):
        syugyo += max(A-int(x/F),0)
    if syugyo <= k:
        return True
    else:
        return False


left = 0
right = a[-1]*f[0]+1
while left < right-1:
    mid = (left+right)//2
    if score(mid):
        right = mid
    else:
        left = mid
print(left+1 if left != 0 else 0)
    
# 計算量は 1+2logN + N*log(2)N <= N*logN < 3.6 * 10^6 
# ぎりぎりセーフ？

Submission status: Time Limit Exceeded

Solution code:
import copy
import math
n, k = list(map(int, input().split()))
A = list(map(int, input().split()))
F = list(map(int, input().split()))
A.sort()
F.sort()
A.reverse()
maxX = max(F) * max(A)
x = [-1 for i in range(maxX + 1)]
def is_able(low, up):
    target = (low + up) // 2
    if low == up - 1:
        return up
    if check(target):
        x[target] = 1
        return is_able(low, target)
    else:
        x[target] = 0
        return is_able(target, up)

def check(time):
    #time が可能かどうか
    practice = copy.deepcopy(k)
    for i in range(n):
        if A[i] * F[i] > time:
            practice -= A[i] - math.floor(time / F[i]) 
            if practice < 0:
                return False
    return True
x[0] = int(check(0))
x[maxX] = int(check(maxX))
print(is_able(-1, maxX))

Submission status: Time Limit Exceeded

Solution code:
import sys
N, K = map(int,input().split())
Alist = list(map(int,input().split()))
Flist = list(map(int,input().split()))
Alist.sort()
sum_Alist = 0
for i in range(N):
    sum_Alist += Alist[i]
print(Alist,Flist,file=sys.stderr)
if sum_Alist <= K:
    print(0)
    exit()
maxtime = max(Alist)*max(Flist)
mintime = -1
print(maxtime,mintime,file=sys.stderr)
while mintime+1 < maxtime:
    mid = (mintime+maxtime)//2
    sum_midlist = 0
    max_midlist = 0
    midlist = [0 for i in range(N)]
    for i in range(N):
        midlist[i] = mid//Flist[i]
    midlist.sort()
    for i in range(N):
        if midlist[i] < Alist[i]:
            sum_midlist += Alist[i]-midlist[i]
    #print(maxtime,mintime,sum_midlist,file=sys.stderr)
    if sum_midlist <= K:
        maxtime = mid
    else:
        mintime = mid
print(maxtime)

Submission status: Time Limit Exceeded

Solution code:
import sys
N, K = map(int,input().split())
Alist = list(map(int,input().split()))
Flist = list(map(int,input().split()))
Alist.sort()
sum_Alist = 0
for i in range(N):
    sum_Alist += Alist[i]
print(Alist,Flist,file=sys.stderr)
if sum_Alist <= K:
    print(0)
    exit()
maxtime = max(Alist)*max(Flist)
mintime = -1
print(maxtime,mintime,file=sys.stderr)
while mintime+1 < maxtime:
    mid = (mintime+maxtime)//2
    sum_midlist = 0
    max_midlist = 0
    midlist = [0 for i in range(N)]
    for i in range(N):
        midlist[i] = mid//Flist[i]
    midlist.sort()
    for i in range(N):
        if midlist[i] < Alist[i]:
            sum_midlist += Alist[i]-midlist[i]
    print(maxtime,mintime,sum_midlist,file=sys.stderr)
    if sum_midlist <= K:
        maxtime = mid
    else:
        mintime = mid
print(maxtime)