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.readline

def sol():
    _, 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(t):
        cnt = 0
        for a, f in zip(A, F):
            ness = t // f
            if a <= ness:
                continue
            cnt += a - ness

        if cnt > K:
            return False
        else:
            return True

    ng = -1
    ok = A[-1] * F[0]

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


sol()

Submission status: Time Limit Exceeded

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

    AF = [(a, f) for a, f in zip(sorted(A), sorted(F, reverse=True))]

    def isOk(T):
        ret = 0
        for a, f in AF:
            m = T // f
            if a > m:
                ret += a - T // f
        return ret <= K

    ok = max(a * f for a, f in AF)
    ng = -1
    while ok - ng > 1:
        mid = (ok + ng) // 2
        if isOk(mid):
            ok = mid
        else:
            ng = mid

    print(ok)

sol()

Submission status: Time Limit Exceeded

Solution code:
def sol():
    _, 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(T):
        ret = 0
        for a, f in zip(A, F):
            ret += max(0, a - T // f)
        return ret <= K

    ok = max(a * f for a, f in zip(A, F))
    ng = -1
    while ok - ng > 1:
        mid = (ok + ng) // 2
        if isOk(mid):
            ok = mid
        else:
            ng = mid

    print(ok)

sol()

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 isOk(T):
    ret = 0
    for a, f in zip(A, F):
        ret += max(0, a - T // f)
    return ret <= K

ok = max(a * f for a, f in zip(A, F))
ng = -1
while ok - ng > 1:
    mid = (ok + ng) // 2
    if isOk(mid):
        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 isOk(T):
    ret = 0
    for a, f in zip(A, F):
        ret += max(0, a - T // f)
    return ret <= K

ok = 10**13
ng = -1
while ok - ng > 1:
    mid = (ok + ng) // 2
    if isOk(mid):
        ok = mid
    else:
        ng = mid

print(ok)

Submission status: Time Limit Exceeded

Solution code:
import sys
import heapq
import math
N, K = map(int, sys.stdin.readline().rstrip().split())
A = list(map(int, sys.stdin.readline().rstrip().split()))
F = list(map(int, sys.stdin.readline().rstrip().split()))
A.sort()
F.sort()

cost = []
for i in range(N):
    cost.append((-A[i] * F[N - 1 - i], A[i], F[N - 1 - i], A[i]))
heapq.heapify(cost)

while K > 0:
    max_1, a_1, f_1, nokori_1 = heapq.heappop(cost)
    max_2, a_2, f_2, nokori_2 = heapq.heappop(cost)
    if max_1 == 0:
        break
    c = math.ceil((max_2 - max_1 + 1) / f_1)
    num = min(K, c)
    if num <= nokori_1:
        heapq.heappush(cost, (min(max_1 + f_1 * num, 0), a_1, f_1, nokori_1 - num))
        heapq.heappush(cost, (max_2, a_2, f_2, nokori_2))
        K -= num
    else:
        heapq.heappush(cost, (min(max_1 + f_1 * a_1, 0), a_1, f_1, nokori_1 - a_1))
        heapq.heappush(cost, (max_2, a_2, f_2, nokori_2))
        break

print(-cost[0][0])

Submission status: Time Limit Exceeded

Solution code:
import sys
import heapq
import math
N, K = map(int, sys.stdin.readline().rstrip().split())
A = list(map(int, sys.stdin.readline().rstrip().split()))
F = list(map(int, sys.stdin.readline().rstrip().split()))
A.sort()
F.sort()

cost = []
for i in range(N):
    cost.append((-A[i] * F[N - 1 - i], A[i], F[N - 1 - i]))
heapq.heapify(cost)

while K > 0:
    max_1, a_1, f_1 = heapq.heappop(cost)
    max_2, a_2, f_2 = heapq.heappop(cost)
    if max_1 == 0:
        break
    c = math.ceil((max_2 - max_1 + 1) / f_1)
    num = min(K, c)
    if num <= a_1:
            heapq.heappush(cost, (min(max_1 + f_1 * num, 0), a_1, f_1))
            heapq.heappush(cost, (max_2, a_2, f_2))
            K -= num
    else:
        heapq.heappush(cost, (min(max_1 + f_1 * a_1, 0), a_1, f_1))
        heapq.heappush(cost, (max_2, a_2, f_2))
        break

print(-cost[0][0])

Submission status: Time Limit Exceeded

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

import numpy as np

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

ok = A[-1] * F[0]
ng = -1

def isOk(x):
  # 時間がxになるためには、A_iをx/F_i以下まで減らす必要がある
  diff = A - x // F
  return sum(np.where(diff > 0, diff, 0)) <= K
  
while (ok - ng)>1:
  mid = (ok + ng) // 2
  if isOk(mid):
    ok = mid
  else:
    ng = mid
print(ok)

Submission status: Time Limit Exceeded

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

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

ok = A[-1] * F[0]
ng = -1

def isOk(x):
  # 時間がxになるためには、A_iをx/F_i以下まで減らす必要がある
  diff = 0
  for i in range(len(A)):
    diff += max(A[i] - x // F[i], 0)
  return diff <= K
  
while (ok - ng)>1:
  mid = (ok + ng) // 2
  if isOk(mid):
    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 solve(n):
    cnt = 0
    for i in range(N):
        cnt += max(0, A[i] - n // F[i])
    return cnt <= K

left = -1
right = 10 ** 12 + 1

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

print(right)

Submission status: Time Limit Exceeded

Solution code:
import bisect
import sys
sys.setrecursionlimit(10**9)

INF = 10**20
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)

    B=[]
    for i in range(N):
        B.append((A[i]*F[i],F[i]))

    B.sort()
    for _ in range(K):
        if not len(B) > 0:
            break
        b,f = B.pop()
        front = (b-f,f)

        if b-f > 0:
            bisect.insort(B,front)

    print(max(B)[0] if len(B) > 0 else 0)
    # print(B)



if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**9)

INF = 10**20
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)

    B=[]
    for i in range(N):
        B.append((A[i]*F[i],F[i]))

    B.sort(reverse=True)
    k = K
    # print(B)
    while k > 0:
        i = 0
        while i < len(B) and B[i][0] == 0:
            i += 1
        if not i < len(B):
            break
        B[i] = (B[i][0]-B[i][1],B[i][1])
        k -= 1
        B.sort(reverse=True)

    print(max(B)[0])
    # print(B)



if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
def isok(t):
    cnt = 0
    for i in range(n):
        cnt += max(a[i] - t // f[i], 0)
        if cnt > k:
            return False
    return True 

n,k = map(int,input().split())
a = list(map(int,input().split()))
f = list(map(int,input().split()))
a.sort(reverse = 1)
f.sort()
ok = a[0] * f[-1]
ng = -1
bool = True
while abs(ok - ng) > 1:
    mid = (ok + ng) // 2
    if isok(mid):
        ok = mid
    else:
        ng = mid
    #print(ng,mid,ok)
print(ok)

Submission status: Time Limit Exceeded

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

n,k = map(int,input().split())
a = list(map(int,input().split()))
f = list(map(int,input().split()))
a.sort(reverse = 1)
f.sort()
ok = a[0] * f[-1]
ng = -1
bool = True
while abs(ok - ng) > 1:
    mid = (ok + ng) // 2
    if isok(mid):
        ok = mid
    else:
        ng = mid
    #print(ng,mid,ok)
print(ok)

Submission status: Time Limit Exceeded

Solution code:
import heapq
n,k=map(int,input().split())
a=sorted(list(map(int,input().split())))
f=sorted(list(map(int,input().split())),reverse=True)
d=[[-a[i]*f[i],f[i]] for i in range(n)]
d.sort(key=lambda x:x[0])
heapq.heapify(d)
for _ in range(k):
  i,j=heapq.heappop(d)
  i+=j
  heapq.heappush(d,[i,j])
ans,_=heapq.heappop(d)
print(max(ans*(-1),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)
end = A[-1] * F[0] + 1
start = -1


def decision(n):
    k = K
    for a, f in zip(A, F):
        while a * f > n:
            a -= 1
            k -= 1
            if k < 0:
                return False
    return True

def calc():
    e = end
    s = start
    while e - s > 1:
        mid = (e + s)//2
        if decision(mid):
            e = mid
        else:
            s = mid
    return e


print(calc())

Submission status: Time Limit Exceeded

Solution code:
import sys

def main():
  input = sys.stdin.readline
  n, k = map(int, input().split())
  a = [int(x) for x in input().split()]
  f = [int(x) for x in input().split()]
  a.sort(reverse=True)
  f.sort()
  
  l, r = -1, pow(10, 12)+1
  while r-l > 1:
    judge = (r+l)//2
    sub = 0
    for i in range(n):
      if a[i]*f[i] <= judge:
        continue
      sub += a[i]-judge//f[i]
    if sub <= k:
      r = judge
    else:
      l = judge
  
  print(r)
  

if __name__ == "__main__":
  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()))
l = -1
r = 10**13

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

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

print(r)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = 10**20
def I(): return int(input())
def F(): return float(input())
def S(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()

def resolve():
    N, K = LI()
    A = LI()
    F = LI()

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

    # 時間tで感触できるか
    def can_complete(t):
        return sum([max(i-t//j, 0) for i, j in zip(A, F)]) <= K

    # for j in range(20):
    #     print(can_complete(j))

    ng = -1
    ok = max(A)*max(F)
    while abs(ok-ng)>1:
        m = (ng+ok)//2
        if can_complete(m):
            ok = m
        else:
            ng = m
    print(ok)

if __name__ == '__main__':
    resolve()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = 10**20
def I(): return int(input())
def F(): return float(input())
def S(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()

def resolve():
    N, K = LI()
    A = LI()
    F = LI()

    A.sort()

    # 時間tで感触できるか
    def can_complete(t):
        # 食べ物のtに間に合う要求コストを越えてる人のみ修行
        return sum([max(i-j, 0) for i, j in zip(A, sorted([t//i for i in F]))]) <= K

    # for j in range(20):
    #     print(can_complete(j))

    ng = -1
    ok = max(A)*max(F)
    while abs(ok-ng)>1:
        m = (ng+ok)//2
        if can_complete(m):
            ok = m
        else:
            ng = m
    print(ok)

if __name__ == '__main__':
    resolve()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = 10**20
def I(): return int(input())
def F(): return float(input())
def S(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()

def resolve():
    N, K = LI()
    A = LI()
    F = LI()

    # 時間tで感触できるか
    def can_complete(t):
        # 食べ物のtに間に合う要求コストを越えてる人のみ修行
        return sum([max(i-j, 0) for i, j in zip(sorted(A), sorted([t//i for i in F]))]) <= K

    # for j in range(20):
    #     print(can_complete(j))

    ng = -1
    ok = max(A)*max(F)
    while abs(ok-ng)>1:
        m = (ng+ok)//2
        if can_complete(m):
            ok = m
        else:
            ng = m
    print(ok)

if __name__ == '__main__':
    resolve()

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(reverse=True)
F.sort()


def judge(x):
    val = 0
    for i in range(N):
        val += max(A[i] - x // F[i], 0)
        if val > K:
            return False
    if val <= K:
        return True


ub = 10**12
lb = 0

for i in range(150):
    x = (ub+lb)/2
    if judge(x):
        ub = x
    else:
        lb = x

print(int(x))

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(reverse=True)
F.sort()


def judge(x):
    val = 0
    for i in range(N):
        val += max(A[i] - x // F[i], 0)
        if val > K:
            return False
    if val <= K:
        return True


ub = 10**12
lb = 0

for i in range(200):
    x = (ub+lb)/2
    if judge(x):
        ub = x
    else:
        lb = x

print(int(x))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
# E

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

# 再起回数上限変更
# sys.setrecursionlimit(1000000)

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

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

q = []
ws = []
cnt = 0

for i in range(N):
    heappush(q, (-A[i]*F[i], A[i], F[i]))
    ws.append(A[i]*F[i])

ws.append(0)
ws.sort(reverse=True)

# print(ws)

for w in ws[1:]:
    # print(w)
    while True:
        # print(w, q)
        val, a, f = heappop(q)
        if val == 0:
            print(-val)
            sys.exit()
        if -val <= w:
            heappush(q, (-a*f, a, f))
            break
        else:
            # a * f < wになるまでaを減らす
            a_n = w // f
            if w== 0:
                diff = 1
            else:
                diff = min(K - cnt, a - a_n)
            cnt += diff
            a -= diff
            heappush(q, (-a*f, a, f))
        # print(w, cnt)
        if cnt >= K:
            break

# print(q)
val, a, f = heappop(q)
print(-val)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
# E

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

# 再起回数上限変更
# sys.setrecursionlimit(1000000)

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

A.sort(reverse=True)
F.sort()
q = []


for i in range(N):
    heappush(q, (-A[i]*F[i], A[i], F[i]))

for k in range(K):
    val, a, f = heappop(q)
    if a == 0:
        print(-val)
        sys.exit()
    else:
        a -= 1
        heappush(q, (-a*f, a, f))

val, a, f = heappop(q)
print(-val)

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

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

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

def is_ok(mid):
    cnt = 0
    for i in range(N):
        if A[i] * F[i] <= mid:
            continue
        else:
            cnt += math.ceil((A[i] * F[i] - mid) / F[i]) # A[i]が1減少するごとにF[i]減るのでF[i]で割る  
    
    return cnt <= K

# okは全員がX以下になる最小値に着地するので、A*F<=10**12 なので＋１して最大のケースにも対応する
ok = 10**12 + 1
# 0ではないことが上で保証されてるので、条件を満たさない最大値の0にしておく
ng = 0
while ok - ng > 1:
    
    mid = (ok + ng) // 2
    #print(ok,ng,mid)
    if is_ok(mid):
        ok = mid
    else:
        ng = mid

#print(ok,ng,mid)
print(ok)

Submission status: Time Limit Exceeded

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

if sum(A) <= K:
    print(0)
else:
    def solve(N, K, A, F):
        A = sorted(A)
        F = sorted(F, reverse=True)
        l = -1
        r = 10**12
        while (r - l) > 1:
            mid = (r + l) // 2
            # 成績がmidだったとして、修行しなければならない回数を算出
            fmid = sum([max(0, a - (mid // f)) for a, f in zip(A, F)])
            if fmid <= K:
                r = mid
            else:
                l = mid
        return(r)
    print(solve(N, K, A, F))

Submission status: Time Limit Exceeded

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

if sum(A) <= K:
    print(0)
else:
    A = sorted(A)
    F = sorted(F, reverse=True)
    l = -1
    r = 10**12
    while (r - l) > 1:
        mid = (r + l) // 2
        # 成績がmidだったとして、修行しなければならない回数を算出
        fmid = sum([max(0, a - (mid // f)) for a, f in zip(A, F)])
        if fmid <= K:
            r = mid
        else:
            l = mid
    print(r)

Submission status: Time Limit Exceeded

Solution code:
def check(A, F, K, x):
    for i in range(len(A)):
        if A[i] * F[i] > x:
            need = (A[i] * F[i] - x + F[i] - 1) // F[i]
            if need > K:
                return False
            K -= need
    return True


N, K = map(int, input().split(' '))
A = list(map(int, input().split(' ')))
F = list(map(int, input().split(' ')))
A.sort()
F.sort()
F = F[::-1]

high, low = 10 ** 13, -1
while high - low > 1:
    mid = (high + low) // 2
    if check(A, F, K, mid):
        high = mid
    else:
        low = mid
print(high)

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 = sorted(a)
f = sorted(f,reverse = True)

hq = []

upper_limit = int(1e+12)
lower_limit = int(0)

def is_ok(checking):
    cost = 0
    for i in range(n):
        cost += max(0,math.ceil((a[i]*f[i]-checking)/f[i]))
    if cost <= k:
        return True
    else:
        return False

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

ok = meguru_bisect(-1, 1e+100) 
print(int(ok))
# 初期値の範囲は取りえる値-1～+1とする←範囲内はok,ngどちらもあり得るため

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 = sorted(a)
f = sorted(f,reverse = True)

hq = []

upper_limit = int(1e+12)
lower_limit = int(0)

def is_ok(checking):
    cost = 0
    for i in range(n):
        cost += max(0,math.ceil((a[i]*f[i]-checking)/f[i]))
    if cost <= k:
        return True
    else:
        return False

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

ok = meguru_bisect(-1, 1e+20) 
print(int(ok))
# 初期値の範囲は取りえる値-1～+1とする←範囲内はok,ngどちらもあり得るため

Submission status: Time Limit Exceeded

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

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

while K >= 0:
  ans = 0
  idx = []
  for n in range(N):
    S = A[n] * F[n]
    if S >= ans:
      ans = S
      idx = n
  K -= 1
  A[idx] -= 1
  if ans == 0:
    break
    
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.sort()
f.sort(reverse=True)
hi=10**12
lo=0
def c(mi):
    tmp=0
    for i,j in zip(a,f):
        if mi//j<i:
            tmp+=i-mi//j
    if tmp<=k:
        return True
    return False
while hi>=lo:
    mi=(hi+lo)//2
    if c(mi):
        hi=mi-1
    else:
        lo=mi+1
print(lo)

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)

max_a = max(A)
max_f = max(F)

left = 0
right = max_a * max_f

while left <= right:
    x = (left + right) // 2

    sum_ = 0
    for i in range(N):
        if A[i] * F[i] > x:
            sum_ += (A[i] - int(x / F[i]))

    if sum_ > K:
        left = x + 1

    if sum_ <= K:
        right = x - 1


print(left)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

a=np.array(input().split(),dtype=np.int64)
f=np.array(input().split(),dtype=np.int64)

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

# r以下にするのに必要修行回数がk以内かどうか
def safe(r):
    return (np.maximum(0,(af-r+f-1)//f)).sum()<=k
    
m=-1
M=10**12

while True:
    pos=(m+M)//2
    if safe(pos):
        M=pos
    else:
        if m==pos:#終わり
            print(M)
            break
        m=pos

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

a=np.array(input().split(),dtype=np.int64)
f=np.array(input().split(),dtype=np.int64)
a.sort()
f.sort()
f=f[::-1]
af=a*f

# r以下にするのに必要修行回数がk以内かどうか
def safe(r):
    return sum(np.maximum(0,af-r+f-1)//f)<=k
    
m=-1
M=10**12

while True:
    pos=(m+M)//2
    if safe(pos):
        M=pos
    else:
        if m==pos:#終わり
            print(M)
            break
        m=pos

Submission status: Time Limit Exceeded

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

import sys
import math
# from string import ascii_lowercase, ascii_upper_case, ascii_letters, digits, hexdigits
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from operator import itemgetter              # itemgetter(1), itemgetter('key')
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product, permutations  # product(iter, repeat=n), permutations(iter[,r])
# from itertools import accumulate             # accumulate(iter[, f])
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict (e.g. list is not allowed)
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from copy import deepcopy                    # to copy multi-dimentional matrix without reference
# from fractions import gcd                    # for Python 3.4 (previous contest @AtCoder)


def main():
    mod = 1000000007                # 10^9+7
    inf = float('inf')              # sys.float_info.max = 1.79...e+308
    inf = 2 ** 64 - 1               # (for fast JIT compile in PyPy) 1.84...e+19
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())
    
    
    n, k = mi()
    A = sorted(lmi(), reverse=True)
    F = sorted(lmi())
    # O(K) * O(lgN)
    # h = [[- A[i] * F[i], F[i]] for i in range(n)]
    # heapify(h)
    # # print(h)
    # for _ in range(k):
    #     minus_val, cost = heappop(h)
    #     plus_val = - minus_val
    #     # plus_val は max heap から取り出した最大値となる
    #     if plus_val == 0:
    #         # もう減らす場所はない。一応戻して抜ける
    #         heappush(h, [plus_val, cost])
    #         break
    #     plus_val -= cost
    #     heappush(h, [- plus_val, cost])
    
    # minus_val, cost = heappop(h)
    # print(- minus_val)

    # O(lgK) * O(N)

    def calc_total_training(A, F, n, key):
        '各メンバーが秒数を key 以下にする必要がある時必要なトレーニングの総数を計算する'
        cnt = 0
        if key < 0:
            return float('inf')
        else:
            for i in range(n):
                diff = max(A[i] * F[i] - key, 0)
                cnt += math.ceil(diff / F[i])
            return cnt
    
    def is_ok(A, F, n, k, key):
        'k 回以下のトレーニングで各メンバーが秒数を key 以下にすることは可能か判定する'
        return calc_total_training(A, F, n, key) <= k
    
    def meguru_bisect(A, F, n, k):
        'k 回以下のトレーニングで達成可能な最短秒数を求める'
        left_sec = -1    # 必ず達成不可能
        right_sec = 10 ** 12    # 必ず達成可能
        while right_sec - left_sec > 1:
            mid = left_sec + (right_sec - left_sec) // 2
            if is_ok(A, F, n, k, mid):
                right_sec = mid
            else:
                left_sec = mid
        return right_sec
    
    print(meguru_bisect(A, F, n, k))



if __name__ == "__main__":
    main()