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:
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 b,g in zip(a,f):
            if b*g>mid:
                l-=b-mid//g
        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.sort()
F.sort(reverse=True)

if sum(A) <= K:
    ans = 0
else:
    high = max([A[i] * F[i] for i in range(N)])
    low = 0
    mid = (high + low) // 2
    while low < mid < high:
        Ki = K
        able = True
        for i in range(N):
            if A[i] * F[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:
n, k = map(int, input().split())
a = sorted(list(map(int, input().split())))
f = sorted(list(map(int, input().split())), reverse=True)

ok, ng = a[-1]*f[0], -1
while ok-ng > 1:
	x = (ok+ng)//2
	tmp = 0
	for i in range(n):
		tmp += max(0, a[i] - x//f[i])
	if tmp > k:
		ng = x
	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)

def isEaten(x):
    temp = 0
    for i in range(N):
        t = x // F[i]
        if t < A[i]:
            temp += (A[i] - t)
    if temp > K:
        return False
    else:
        return True


def bitSearch(r, l):
    m = (r+l) // 2
    if m == l:
        if isEaten(l):
            print(l)
        else:
            print(r)
        exit()
    elif isEaten(m):
        bitSearch(m, l)
    else:
        bitSearch(r, m)


target = max([A[i]*F[i] for i in range(N)])
bitSearch(target, 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()))

Asum = sum(A)

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

def test(x):
    res = 0
    for i in range(N):
        res += max(0,Asort[i]-x//Fsort[i])
    return res <= K

left = -1
right = 10**13

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

ans = right

print(ans)

Submission status: Time Limit Exceeded

Solution code:

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

ans=int(0)
l.sort()
f.sort()
f.reverse()
t=[]

for i in range(n):

    t.append(l[i]*f[i])

for i in range(k):

    c=t.index(max(t))
    l[c] -=1
    t[c]=l[c]*f[c]
    if not c==0:
        if l[c] < l[c-1]:
            l[c], l[c-1] =l[c-1], l[c]
            t[c-1]=l[c-1]*f[c-1]

ans=max(t)

if ans>=0:
    print(ans)
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)
	upper = max(time)

	def is_ok(x):  # 時間をx以下にできるか？
		tmp = 0
		for i in range(N):
			if time[i] <= x:
				continue
			else:
				tmp += ceil((time[i]-x)/F[i])
			if tmp > K:
				return False
		else:
			return True

	min_ = -1
	max_ = upper
	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:
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][-1] > 0:
        a.pop(a.index(d[0][-1]))
        d[0][-1] -= 1
        a.insert(bisect.bisect_right(a, d[0][-1]) ,d[0][-1])
        d = [[f[i]*a[i], f[i], a[i]] for i in range(n)]
        d.sort(reverse = True)
    else:
        break
print(d[0][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)
	upper = max(time)

	def is_ok(x):  # 時間をx以下にできるか？
		tmp = 0
		for i in range(N):
			if time[i] <= x:
				pass
			else:
				tmp += ceil((time[i]-x)/F[i])
		if tmp > K:
			return False
		else:
			return True

	min_ = -1
	max_ = upper
	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:
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

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)
upper = max(time)

def is_ok(x):  # 時間をx以下にできるか？
	tmp = 0
	for i in range(N):
		if time[i] <= x:
			pass
		else:
			tmp += ceil((time[i]-x)/F[i])
	if tmp > K:
		return False
	else:
		return True

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

print(max_)

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

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)

def is_ok(x):  # 時間をx以下にできるか？
	tmp = 0
	for i in range(N):
		if time[i] <= x:
			pass
		else:
			tmp += ceil((time[i]-x)/F[i])
	if tmp > K:
		return False
	else:
		return True

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

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)
mul = [A[i]*F[i] for i in range(N)]

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

ma = 2**40
mi = 0
while 1:
    tgt = mi + (ma - mi)//2
    num = 0
    for i in range(N):
        tmp = (mul[i] - tgt + F[i] - 1) // F[i]
        if tmp < 0:
            tmp = 0
        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:
import sys
input = sys.stdin.readline


# 解説AC
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 check(mid):
    k = K
    # 全員が目標値 mid を下回るまで修行できるか？
    for i in range(N):
        if A[i] * F[i] > mid:
            # x: 必要な修行回数
            x = A[i] - mid // F[i]
            k -= x
            # 誰かが修行できなかった ⇒ その目標値は達成不可能
            if k < 0:
                return False
    return True


def main():
    H = []
    for i in range(N):
        H.append(A[i]*F[i])
    # lb := 条件を満たさない最大, ub := 条件を満たす最小
    lb, ub = -1, max(H)
    while ub - lb > 1:
        mid = (lb + ub)//2
        if check(mid):
            ub = mid
        else:
            lb = mid
    print(ub)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import copy
import numpy as np
N,K=map(int, input().split())
A=np.array(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
  
F = np.array(F)
print(max(furi*F))

Submission status: Time Limit Exceeded

Solution code:
import bisect

n, k = [int(x) for x in input().split()]
xs   = [int(x) for x in input().split()]
fs   = [int(x) for x in input().split()]
ys   = [0] * n
l    = 0
r    = 0

xs.sort()
fs.sort(reverse = True)

for i in range(0, n):
	ys[i] = xs[i] * fs[i]
	r     = max(r, ys[i])

def check(x, y):
	for i in range(0, n):
		if x < ys[i]:
			a = xs[i] - x // fs[i]
			if a <= y:
				y -= a
			else:
				return False
	return True

while l <= r:
	m = (l + r) // 2
	if check(m, k):
		r = m - 1
	else:
		l = m + 1

if check(l, k) == True:
	print(l)
else:
	print(r)

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()
    F.sort(reverse=True)
    
    def count(m):
        ret=0
        for a,f in zip(A,F):
            ret+=max(0,a-(m//f))
        return ret
    ng=-1
    ok=10**12+1
    while ok-ng>1:
        mid=(ok+ng)//2
        cnt=count(mid)
        if cnt<=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 = list(map(int, input().split()))
f = list(map(int, input().split()))
a.sort()
f.sort(reverse = True)
a = [[f[i]*a[i], f[i], a[i]] for i in range(n)]
a.sort(reverse = True)
for i in range(k):
    if a[0][-1] > 0:
        a[0][-1] -= 1
        a = [a[i][-1] for i in range(n)]
        a.sort()
        a = [[f[i]*a[i], f[i], a[i]] for i in range(n)]
        a.sort(reverse = True)
    else:
        break
print(a[0][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

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)

def is_ok(x):  # 時間をx以下にできるか？
	tmp = 0
	for i in range(N):
		if time[i] <= x:
			pass
		else:
			tmp += ceil((time[i]-x)/F[i])
	if tmp > K:
		return False
	else:
		return True

def nibutan(min_, max_):
	if min_+1 >= max_:
		if is_ok(min_):
			return min_
		else:
			return max_
	else:
		search = (min_+max_)//2
		# print(min_, max_, search)
		if is_ok(search):
			max_ = search
		else:
			min_ = search
		return nibutan(min_, max_)

print(nibutan(0, 10**18))

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))
  kk=min(k,10**12)
  for i in range(kk):
    tmp,key=heappop(q)
    heappush(q,(tmp+key,key))
  ans,key=heappop(q)
  if -ans>=0:
    print(-ans)
  else:
    print(0)
abc144c()

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 judge(x):
    res=K
    for n in range(N):
        over=max(A[n]*F[n]-x,0)
        res-=-(-over//F[n])
    return res>=0

left=-1
right=10**12*+1
while left+1<right:
    mid=(left+right)//2
    if judge(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)

def judge(x):
    res=K
    for n in range(N):
        over=max(A[n]*F[n]-x,0)
        res-=-(-over//F[n])
    return res>=0

def bin_search(left,right):
    if left+1==right:
        return right
    else:
        mid=(left+right)//2
        if judge(mid):
            return bin_search(left,mid)
        else:
            return bin_search(mid,right)
print(bin_search(-1,10**12+1))

Submission status: Time Limit Exceeded

Solution code:
import bisect

n, k = [int(x) for x in input().split()]
xs   = [int(x) for x in input().split()]
fs   = [int(x) for x in input().split()]
ys   = [0] * n

xs.sort()
fs.sort(reverse = True)

for i in range(0, n):
	ys[i] = xs[i] * fs[i]

l = 0
r = xs[-1] * fs[0]

def check(x, y):
	for i in range(0, n):
		if x < ys[i]:
			a = xs[i] - x // fs[i]
			if a <= y:
				y -= a
			else:
				return False
	return True

while l <= r:
	m = (l + r) // 2
	if check(m, k):
		r = m - 1
	else:
		l = m + 1

if check(l, k) == True:
	print(l)
else:
	print(r)

Submission status: Time Limit Exceeded

Solution code:
#import numpy as np
input = raw_input

def argmax(l):
    max_ = max(l)
    max_i = l.index(max_)
    return max_i

n, k = map(int, input().split(" "))
A_list = sorted(map(int, input().split(" ")))
F_list = sorted(map(int, input().split(" ")), reverse=True)

#print("A_list", A_list)
#print("F_list", F_list)

mults = sorted([[a, f, a*f] for a, f in zip(A_list, F_list)], key=lambda x: -x[2])
#print(mults)

costs = []

do_break = False
for i in range(n):
    if i == n-1:
        kijun = 0
    else:
        kijun = mults[i+1][2]
    targets = mults[:i+1]

    cost = 0
    for a, b, mult in targets:
        new_a = kijun // b
        diff = a - new_a
        cost += diff
    costs.append(cost)
    if cost >= k:
        break_i = i
        do_break = True
        break

#print(costs, do_break)

if not do_break:
    print(0)
#if break_i >= 1:
else:
    i = break_i - 1
    kijun = mults[i+1][2]
    targets = mults[:i+1]

    cost = 0
    new_mults = []
    new_as = []
    bs = []
    for a, b, mult in targets:
        new_a = kijun // b
        diff = a - new_a
        cost += diff
        new_mults.append(new_a * b)
        new_as.append(new_a)
        bs.append(b)

    a, b, mult = mults[break_i]
    new_mults.append(mult)
    new_as.append(a)
    bs.append(b)
    #print("new_mults", new_mults)

    nokori_k = k - cost

    #print(new_as, bs)
    for i in range(nokori_k):
        #i = np.argmax(new_mults)
        i = argmax(new_mults)
        new_as[i] -= 1
        new_mult = new_as[i] * bs[i]
        new_mults[i] = new_mult


    out = max(max(new_mults), 0)
    print(out)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
from datetime import date, timedelta
from heapq import*
import math
from collections import defaultdict, Counter, deque
import sys
from bisect import *
import itertools
import copy
sys.setrecursionlimit(10 ** 7)
MOD = 10 ** 9 + 7




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

    def ok(v):
        cnt = 0
        sa = 0
        for i in range(n):
            t = a[i]*f[i]
            if v - t >= 0:
                continue
            cnt += a[i] - (v // f[i])
            if cnt > k:
                break
        
        if cnt <= k:
            return True
        else:
            return False





    l, r = 0, 10 ** 19
    for i in range(200):
        m = (l + r) / 2
        if ok(m):
            r = m
        else:
            l = m
    print(int(m))

    
            
    

    

    

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
from datetime import date, timedelta
from heapq import*
import math
from collections import defaultdict, Counter, deque
import sys
from bisect import *
import itertools
import copy
sys.setrecursionlimit(10 ** 7)
MOD = 10 ** 9 + 7




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

    def ok(v):
        cnt = 0
        sa = 0
        for i in range(n):
            t = a[i]*f[i]
            if v - t >= 0:
                continue
            cnt += a[i] - (v//f[i])
        
        if cnt <= k:
            return True
        else:
            return False





    l, r = 0, 10 ** 19
    for i in range(200):
        m = (l + r) / 2
        if ok(m):
            r = m
        else:
            l = m
    print(int(m))

    
            
    

    

    

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import math

def cal(sum_, F, N, K, d):
    count = 0
    for i in range(N):
        if sum_[i] > d:
            count += math.ceil((sum_[i] - d) / F[i])
            if count > K:
                #作ることができない
                return False
    return True


def main():
    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)
    sum_ = []
    for i in range(N):
        sum_.append(A[i] * F[i])

    right = 10 ** 12
    left = 0
    count = 0
    pre_mid = 0
    while count < 100:
        mid = (right + left) // 2
        if pre_mid == mid:
            break
        if cal(sum_, F, N, K, mid):
            # midを小さくすることができる
            right = mid
        else:
            # midを大きくしなければならない
            left = mid + 1
        pre_mid = mid
        count += 1
    print(mid)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
a = sorted(map(int, input().split()))
f = sorted(map(int, input().split()))
time = [f[i] * a[-i-1] for i in range(n)]

sup = max(time)
inf = 0
while sup > inf:
  x = (sup + inf) // 2
  train = sum([(max([0, time[i] - x]) + f[i] - 1) // f[i] for i in range(n)])
  if k < train:
    inf = x + 1
  else:
    sup = x
print(sup)

Submission status: Time Limit Exceeded

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)
maxAF = max([A*F for A, F in zip(As, Fs)])

def isOK(X):
    rest = K
    for A, F in zip(As, Fs):
        if A*F > X:
            A2 = X//F
            d = A-A2
            if d > rest:
                return False
            rest -= d
    return True

ng, ok = -1, maxAF
while abs(ok-ng) > 1:
    mid = (ng+ok) // 2
    if isOK(mid):
        ok = mid
    else:
        ng = mid

print(ok)

Submission status: Time Limit Exceeded

Solution code:
import math

def cal(sum_, F, N, K, d):
    count = 0
    for i in range(N):
        if sum_[i] > d:
            count += math.ceil((sum_[i] - d) / F[i])
            if count > K:
                #作ることができない
                return False
    return True


def main():
    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)
    sum_ = []
    for i in range(N):
        sum_.append(A[i] * F[i])

    right = 10 ** 12
    left = 0
    count = 0
    while count < 100:
        mid = (right + left) // 2
        if cal(sum_, F, N, K, mid):
            # midを小さくすることができる
            right = mid
        else:
            # midを大きくしなければならない
            left = mid + 1
        count += 1
    print(mid)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n, k = map(int, input().split(" "))
A_list = sorted(map(int, input().split(" ")))
F_list = sorted(map(int, input().split(" ")), reverse=True)

#print("A_list", A_list)
#print("F_list", F_list)

mults = sorted([[a, f, a*f] for a, f in zip(A_list, F_list)], key=lambda x: -x[2])
#print(mults)

costs = []

do_break = False
for i in range(n):
    if i == n-1:
        kijun = 0
    else:
        kijun = mults[i+1][2]
    targets = mults[:i+1]

    cost = 0
    for a, b, mult in targets:
        new_a = kijun // b
        diff = a - new_a
        cost += diff
    costs.append(cost)
    if cost >= k:
        break_i = i
        do_break = True
        break

#print(costs, do_break)

if not do_break:
    print(0)
#if break_i >= 1:
else:
    i = break_i - 1
    kijun = mults[i+1][2]
    targets = mults[:i+1]

    cost = 0
    new_mults = []
    new_as = []
    bs = []
    for a, b, mult in targets:
        new_a = kijun // b
        diff = a - new_a
        cost += diff
        new_mults.append(new_a * b)
        new_as.append(new_a)
        bs.append(b)

    a, b, mult = mults[break_i]
    new_mults.append(mult)
    new_as.append(a)
    bs.append(b)
    #print("new_mults", new_mults)

    nokori_k = k - cost

    #print(new_as, bs)
    for i in range(nokori_k):
        i = np.argmax(new_mults)
        new_as[i] -= 1
        new_mult = new_as[i] * bs[i]
        new_mults[i] = new_mult


    out = max(max(new_mults), 0)
    print(out)

Submission status: Time Limit Exceeded

Solution code:
import bisect

n, k = [int(x) for x in input().split()]
xs   = [int(x) for x in input().split()]
fs   = [int(x) for x in input().split()]

xs.sort()
fs.sort(reverse = True)

l = 0
r = xs[-1] * fs[0]

def check(x, y):
	for i in range(0, n):
		if x < xs[i] * fs[i]:
			a = xs[i] - x // fs[i]
			if a <= y:
				y -= a
			else:
				return False
	return True

while l <= r:
	m = (l + r) // 2
	if check(m, k):
		r = m - 1
	else:
		l = m + 1

if check(l, k) == True:
	print(l)
else:
	print(r)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
from math import ceil
from heapq import heappush, heappop, heapreplace

def solve():
    N, K = map(int, input().split())
    A = sorted(map(int, input().split()))
    F = sorted(map(int, input().split()), reverse=1)
    level = {}
    hqv = set()
    for a,f in zip(A,F):
        if -a*f not in hqv:
            hqv.add(-a*f)
            level[-a*f] = [f]
        else:
            level[-a*f].append(f)
    hqv = sorted(hqv)

    def check(X):
        return K < sum(sum(ceil((X-c)/f) for f in level[c]) for c in filter(X.__gt__ , hqv))

    search_range = [hqv[0], 1]
    update_range = lambda mid: search_range.__setitem__(check(mid), mid)
    for _ in range(search_range[0].bit_length()+1):
        update_range(sum(search_range)//2)

    return -search_range[0]

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

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

def search(x, k, A, F):
    for a, f in zip(A, F):
        time = a * f
        if time <= x:
            continue
        else:
            dif = time - x
            training = int(math.ceil(dif/f))
            k -= training

        if k < 0:
            return False
    return True


A.sort()
F.sort(reverse=True)
r= max([a*f for a, f in zip(A, F)])
l = 0
while l < r:
    candidate = (r+l)//2
    if search(candidate, k, A, F):
        r = candidate
    else:
        l = candidate + 1

print(r)

Submission status: Time Limit Exceeded

Solution code:
from math import ceil
N, K = map(int, input().split())
A = list(map(int, input().split()))
F = list(map(int, input().split()))
A.sort()
F.sort(reverse=True)

lo, hi = 0, max(a*f for (a, f) in zip(A,F))
while lo < hi:
    mid = (lo + hi)//2
    rsd = K
    possible = True
    for a, f in zip(A,F):
        rsd -= ceil(max(a*f-mid, 0)/f)
        if rsd < 0:
            possible = False
            break
    if possible:
        hi = mid
    else:
        lo = mid+1

print(lo)

Submission status: Time Limit Exceeded

Solution code:
def test(x):
	cost = 0
	for i in range(N):
		cost += max(0, A[i] - (x // F[i]))
	return cost <= K

if __name__ == "__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)
	left = -1
	right = 10**13
	while left + 1 < right:
		mid = (left + right) // 2
		if test(mid):
			right = mid
		else:
			left = mid
	ans = right
	print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from operator import itemgetter
input = sys.stdin.readline

_n, _k = map(int, input().split())
_a = input()[:-1]
_f = input()[:-1]
alist = [item for item in map(int, _a.split())]
flist = [item for item in map(int, _f.split())]


def chker(costs, diffs, max_k):
    if sum(costs) <= max_k:
        print(0)
        return

    costs.sort()
    diffs.sort(reverse=True)
    sclist = sorted([[item1, item2, item1 * item2] for item1, item2 in zip(costs, diffs)], key=itemgetter(2), reverse=True)
    for k in range(max_k, 0, -1):
        sclist[0][0] = sclist[0][0] - 1
        if sclist[0][0] == 0:
            sclist = sclist[1:]
        else:
            sclist[0][2] = sclist[0][0] * sclist[0][1]
            sclist.sort(key=itemgetter(2), reverse=True)

    print(sclist[0][2])


chker(alist, flist, _k)

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

Submission status: Time Limit Exceeded

Solution code:

n, k = map(int, input().split())
l=list(map(int, input().split()))
f=list(map(int, input().split()))
t=[]
ans=int(0)
l.sort()
f.sort()
f.reverse()

for i in range(n):
    t.append(l[i]*f[i])
for i in range(k+1):

    l[t.index(max(t))] -=1
    while True:
        a=t.index(max(t))
        b=l[t.index(max(t))]

        if b<l[a-1]:
            l[a]=l[a-1]
            a -=1
        else:
            l[a]=b


ans=max(t)
if ans>=0:
    print(ans)
else:
    print(0)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10000000)
import heapq
import math

def main():
    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)

    num = 0
    sum_ = []
    for i in range(N):
      sum_.append(A[i] * F[i])
    left = 0
    right = 10 ** 12
    while(num < 100):
        number = 0
        mid = (left + right) // 2
        # print(mid)
        for i in range(len(A)):
            if sum_[i] <= mid:
                continue
            else:
                number += math.ceil((sum_[i] - mid) / F[i])
            # print(number)
        if number > K:
            # 最大値をmidより小さくできない -> 最大値はもっとでかい
            left = mid + 1
        else:
            right = mid
        num += 1
    print(mid)
                
        



if __name__ == '__main__':
    main()