Problem:


Score: 500 points

Problem Statement

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

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

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

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

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

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

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

Constraints

All values in input are integers.

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

0 \leq K \leq 10^{18}

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

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

Input

Input is given from Standard Input in the following format:

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

Output

Print the minimum possible score of the team.

Sample Input 1

3 5
4 2 1
2 3 1

Sample Output 1

2

They can achieve the score of 2, as follows:

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

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

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

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

Sample Input 2

3 8
4 2 1
2 3 1

Sample Output 2

0

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

Sample Input 3

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

Sample Output 3

12



Sample input:
3 5
4 2 1
2 3 1


Sample output:
2

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
inputs= sys.stdin.buffer.readlines
#rstrip().decode('utf-8')

#import math
import numpy as np
#import operator
#from heapq import heapify,heappop,heappush
#from math import gcd
#from fractions import gcd
#from collections import deque
#from collections import defaultdict
#from collections import Counter
#from itertools import accumulate
#from itertools import groupby
#from itertools import permutations
#from itertools import combinations
#from scipy.sparse import csr_matrix
#from scipy.sparse.csgraph import floyd_warshall
#from scipy.sparse.csgraph import csgraph_from_dense
#from scipy.sparse.csgraph import dijkstra
#sys.setrecursionlimit(10**7)

#map(int,input().split())

def main():
	N,K=map(int,input().split())
	AF=np.array(read().split(),np.int64)
	A,F=np.split(AF,2)
	A.sort()
	F.sort()
	F=F[::-1]
	
	lt=0
	rt=10**12+1
	
	Asum=A.sum()
	
	while rt-lt>1:
		mid=(rt+lt)//2
		if Asum-np.minimum(A,mid//F).sum()<=K:
			rt=mid
		else:
			lt=mid
	print(rt if Asum-K>0 else 0)
	
if __name__ == '__main__':
	main()

Submission status: Accepted

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

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

l = -1
r = 10 ** 12


def ok(c):
    s = 0
    for a, f in zip(A, F):
        s += max(0, a - c//f)
    return s <= K


while r - l > 1:
    c = (l+r)//2
    if ok(c):
        r = c
    else:
        l = c

print(r)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
inputs= sys.stdin.buffer.readlines
#rstrip().decode('utf-8')

#import math
import numpy as np
#import operator
#from heapq import heapify,heappop,heappush
#from math import gcd
#from fractions import gcd
#from collections import deque
#from collections import defaultdict
#from collections import Counter
#from itertools import accumulate
#from itertools import groupby
#from itertools import permutations
#from itertools import combinations
#from scipy.sparse import csr_matrix
#from scipy.sparse.csgraph import floyd_warshall
#from scipy.sparse.csgraph import csgraph_from_dense
#from scipy.sparse.csgraph import dijkstra
#sys.setrecursionlimit(10**7)

#map(int,input().split())

def main():
	NKAF=np.array(read().split(),np.int64)
	N=NKAF[0]
	K=NKAF[1]
	AF=NKAF[2:]
	A,F=np.split(AF,2)
	A.sort()
	F.sort()
	F=F[::-1]
	
	lt=0
	rt=10**12+1
	
	Asum=A.sum()
	
	while rt-lt>1:
		mid=(rt+lt)//2
		if Asum-np.minimum(A,mid//F).sum()<=K:
			rt=mid
		else:
			lt=mid
	print(rt if Asum-K>0 else 0)
	
if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
inputs= sys.stdin.buffer.readlines
#rstrip().decode('utf-8')

#import math
import numpy as np
#import operator
#from heapq import heapify,heappop,heappush
#from math import gcd
#from fractions import gcd
#from collections import deque
#from collections import defaultdict
#from collections import Counter
#from itertools import accumulate
#from itertools import groupby
#from itertools import permutations
#from itertools import combinations
#from scipy.sparse import csr_matrix
#from scipy.sparse.csgraph import floyd_warshall
#from scipy.sparse.csgraph import csgraph_from_dense
#from scipy.sparse.csgraph import dijkstra
#sys.setrecursionlimit(10**7)

#map(int,input().split())

def main():
	NKAF=np.array(read().split(),np.int64)
	N=NKAF[0]
	K=NKAF[1]
	AF=NKAF[2:]
	A,F=np.split(AF,2)
	A.sort()
	F.sort()
	F=F[::-1]
	
	lt=0
	rt=10**12+1
	
	Asum=sum(A)
	
	while rt-lt>1:
		mid=(rt+lt)//2
		if Asum-np.minimum(A,mid//F).sum()<=K:
			rt=mid
		else:
			lt=mid
	print(rt if Asum-K>0 else 0)
	
if __name__ == '__main__':
	main()

Submission status: Accepted

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

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

l = -1
r = A[-1] * F[0]


def ok(c):
    s = 0
    for a, f in zip(A, F):
        s += max(0, a - c//f)
    return s <= K


while r - l > 1:
    c = (l+r)//2
    if ok(c):
        r = c
    else:
        l = c

print(r)

Submission status: Accepted

Solution code:
(_,K),*T=[map(int,t.split())for t in open(0)]
A,B=map(sorted,T)
d=[0,2**40]
exec("i=sum(d)//2;d[-sum(min(0,i-a*b)//b for a,b in zip(A,B[::-1]))<=K]=i;"*41)
print(d[1])

Submission status: Accepted

Solution code:
(_,K),*T=[map(int,t.split())for t in open(0)]
A,B=map(sorted,T)
m,M,i=0,2**40,1
exec("i,M,m=((i+m)//2,i,m) if -sum(min(0,i-a*b)//b for a,b in zip(A,B[::-1]))<=K else((i+M)//2,M,i);"*41)
print(M)

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
X=[(b,a*b)for a,b in zip(sorted(list(map(int,input().split()))),sorted(list(map(int,input().split())))[::-1])]
m,M,i=0,2**40,1
exec("i,M,m=((i+m)//2,i,m) if -sum(min(0,i-c)//b for b, c in X)<=K else((i+M)//2,M,i);"*50)
print(M)

Submission status: Accepted

Solution code:
import math
N,K=map(int,input().split())
X=[(b,a*b)for a,b in zip(sorted(list(map(int,input().split()))),sorted(list(map(int,input().split())))[::-1])]
m,M,i=0,10**12,1
exec("i,M,m=((i+m)//2,i,m) if sum(math.ceil(max(0,c-i)/b)for b, c in X)<=K else((i+M)//2,M,i);"*50)
print(M)

Submission status: Accepted

Solution code:
import sys
import numpy as np
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)


def main():
    N, K = map(int, input().split())
    A = np.array(list(map(int, input().split())))
    F = np.array(list(map(int, input().split())))

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

    left = -1
    right = 10 ** 12
    while left+1 < right:
        mid = (left+right) // 2
        if Asum - np.minimum(A, mid//F).sum() <= K:
            right = mid
        else:
            left = mid
    print(right)


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

Submission status: Accepted

Solution code:
import math
N,K=map(int,input().split())
X=[(b,a*b)for a,b in zip(sorted(list(map(int,input().split()))),sorted(list(map(int,input().split())))[::-1])]
min_i, max_i, index = 0, 10**12, 1
while True:
    index, max_i, min_i = ((index-1 + min_i)//2, index-1, min_i) if sum(math.ceil(max(0,c-index)/b)for b, c in X)<=K else((index+1 + max_i)//2, max_i, index+1)
    if min_i > max_i:
        print(min_i)
        break

Submission status: Accepted

Solution code:
import math
N, K = map(int, input().split())
BCs = [(b,a*b) for a,b in zip(sorted(list(map(int, input().split()))), sorted(list(map(int, input().split())))[::-1])]

def f(target):
    return sum(math.ceil(max(0, c - target)/b)for b, c in BCs)<=K

if __name__ == '__main__':
    min_i, max_i, index = 0, 10**12, 1
    while True:
        index, max_i, min_i = ((index-1 + min_i)//2, index-1, min_i) if f(index) else ((index+1 + max_i)//2, max_i, index+1)
        if min_i > max_i:
            print(min_i)
            break

Submission status: Accepted

Solution code:
import math
N, K = map(int, input().split())
As = sorted(list(map(int, input().split())))
Bs = sorted(list(map(int, input().split())))[::-1]
Cs = [a*b for a, b in zip(As, Bs)]
BCs = list(zip(Bs, Cs))

def func(target):
    r = 0
    for b, c in BCs:
        r += math.ceil(max(0, c - target) / b)
    return r <= K

if __name__ == '__main__':
    min_i, max_i, index = 0, max(Cs)+1, 1
    while True:
        if func(index):
            index, max_i = (index-1 + min_i)//2, index-1
        else:
            index, min_i = (index+1 + max_i)//2, index+1
        if min_i > max_i:
            print(min_i)
            break

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    return

#B
def B():
    return

#C
def C():
    return

#D
def D():
    return

#E
def E():
    def solve(m):
        a1 = a[::-1]
        f1 = f[::1]
        res = 0
        for i in range(n):
            if a1[i] * f1[i] <= m:
                continue
            k = m // f1[i]
            res += a1[i] - k
            if res > K:
                return False
        return True

    n, K = LI()
    a = LI()
    a.sort()
    f = LI()
    f.sort()
    ok = max(a) * max(f)
    ng = -1
    while ok - ng > 1:
        mid = (ok + ng) // 2
        if solve(mid):
            ok = mid
        else:
            ng = mid
    print(ok)
    return

#F
def F():
    return


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

Submission status: Accepted

Solution code:
import numpy as np

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

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

    A.sort()
    F.sort()
    A = A[::-1]
    
    cost = A * F
    down = -1
    up = np.max(cost)
    while up > down + 1:
        mid = (down + up) // 2
        if np.sum(np.where(cost > mid, np.ceil((cost - mid) / F), 0)) <= K:
            up = mid
        else:
            down = mid
    
    print(up)
    

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n,k=list(map(int,input().split()))
a=sorted(list(map(int,input().split())))
f=sorted(list(map(int,input().split())),reverse=True)
b = [a[i]*f[i] for i in range(n)]

def judgement(x):
    judge = -1
    cnt = 0
    for i in range(n):
        if b[i]>x:
            cnt += -((x-b[i])//f[i])
        if cnt > k:
            judge = False
            break
    if cnt <= k:
        judge = True
    return judge

low=0
high=max(b)
while low<high:
    mid = (low + high)//2
    if judgement(mid) == False:
        low=mid+1
    else:
        high=mid
print(low)

Submission status: Accepted

Solution code:
import math
n,k = map(int,input().split())
A = list(map(int,input().split()))
F = list(map(int,input().split()))
A.sort()
F.sort(reverse = True)
e = [0]*n
for i in range(n):#時間をとりあえず計算
    e[i] = A[i]*F[i]
    
def s(e,x):
    kk=0
    for i in range(n):
        if e[i] < x:
            continue
        else:
            kk += math.ceil((e[i]-x)/F[i]) #xになるような値をkkに足す
    if kk > k:#kkの値がkを超えるとそのxを最小にはできない
        return False
    else:
        return True

#最適なxを二分探索する
sma = 0
big = A[-1]*F[0]

while big != sma:
    mid = (big+sma)//2
    if s(e,mid):#midはできる
        big = mid
    else:#midでできない＝それより大きくないとダメ
        sma = mid + 1
print(sma)

Submission status: Accepted

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

_n, _k = map(int, input().split())
alist = [int(item) for item in input().split()]
flist = [int(item) for item in input().split()]


def chker(costs, diffs, max_k):
	costs = np.sort(costs)[::-1]
	diffs = np.sort(diffs)
	
	_min, _max = 0, 10 ** 12
	while _min < _max:
		_mid = (_min + _max) // 2
		cnt = costs - _mid // diffs
		if cnt[cnt > 0].sum() <= max_k:
			_max = _mid
		else:
			_min = _mid + 1


	print(_min)


chker(alist, flist, _k)

Submission status: Accepted

Solution code:
import numpy as np
N,K = [int(x) for x in input().split()]
A = np.array([int(x) for x in input().split()])
F = np.array([int(x) for x in input().split()])
A.sort()
Asum=np.sum(A)
F.sort();F=F[::-1]
left=-1 #不可能
right=10**20 #可能
while left+1<right:
  mid =(left+right)//2
  if Asum-np.minimum(A,mid//F).sum()<=K:
    right=mid
  else:
    left=mid
print(right)

Submission status: Accepted

Solution code:
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()))))

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

left = - 1
right = 10**12

def f(x):
    l = x//F
    return A[A > l].sum() <= K + l[A > l].sum()

while right - left > 1:
    mid = (left + right)//2
    if f(mid):
        right = mid
    else:
        left = mid
    
print(right)

Submission status: Accepted

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

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

left = - 1
right = 10**12

def f(x):
    l = x//F
    return A[A > l].sum() <= K + l[A > l].sum()

while right - left > 1:
    mid = (left + right)//2
    if f(mid):
        right = mid
    else:
        left = mid
    
print(right)

Submission status: Accepted

Solution code:
# 時間内に解ける
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))

left = - 1
right = 10**12

def f(x):
    #return np.maximum(0, A - x//F) .sum()<= K
    return A.sum() - np.minimum(A, x//F).sum()<= K

while right - left > 1:
    mid = (left + right)//2
    if f(mid):
        right = mid
    else:
        left = mid
    
print(right)

Submission status: Accepted

Solution code:
import numpy as np
#import math
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))



left = - 1
right = 10**12

def f(x):
    l = x//F
    return A[A > l].sum() <= K + l[A > l].sum()

while right - left > 1:
    mid = (left + right)//2
    if f(mid):
        right = mid
    else:
        left = mid
    
print(right)

Submission status: Accepted

Solution code:
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))

left = - 1
right = 10**12

def f(x):
    return np.maximum(0, A - x//F) .sum()<= K

while right - left > 1:
    mid = (left + right)//2
    if f(mid):
        right = mid
    else:
        left = mid
    
print(right)

Submission status: Accepted

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

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 7)
INF = 10 ** 18
MOD = 10 ** 9 + 7

def bisearch_min(mn, mx, func):
    """ 条件を満たす最小値を見つける二分探索 """

    ok = mx
    ng = mn
    while ng+1 < ok:
        mid = (ok+ng) // 2
        if func(mid):
            # 下を探しに行く
            ok = mid
        else:
            # 上を探しに行く
            ng = mid
    return ok

N, K = MAP()
A = LIST()
B = LIST()

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

def check(m):
    k = 0
    for i, a in enumerate(A):
        b = B[i]
        k += max(ceil(a - m/b), 0)
        if k > K:
            return False
    return True

print(bisearch_min(-1, INF, check))

Submission status: Accepted

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

a.sort()
f.sort()
a = a[::-1]
kaketa = []
for i in range(n):
    kaketa.append(a[i]*f[i])

left = 0
right = max(kaketa)

while True:
    jiku = (left+right)//2
    kaisuu = 0
    for i in range(n):
        if kaketa[i] - jiku > 0:
            if (kaketa[i] - jiku) % f[i] != 0:
                kaisuu += (kaketa[i] - jiku) // f[i] + 1
            else:
                kaisuu += (kaketa[i] - jiku) // f[i]
    if kaisuu > k:
        left = jiku
    else:
        right = jiku
    if right - left == 1:
        break

if sum(a) <= k:
    print(0)
else:
    print(right)

Submission status: Accepted

Solution code:
# ABC144E - Gluttony
def binary_search(upper_bound: int = 1 << 60, lower_bound: int = -1) -> int:
    ok, ng = upper_bound, lower_bound
    while abs(ok - ng) > 1:
        mid = (ok + ng) // 2
        if check(mid):  # condition
            ok = mid
        else:
            ng = mid
    return ok


def check(x: int) -> bool:
    cost = sum(a - x // f for a, f in zip(A, F) if a * f > x)
    return cost <= K


def main():
    global K, A, F
    N, K, *AF = map(int, open(0).read().split())
    A, F = sorted(AF[:N]), sorted(AF[N:], reverse=1)
    ans = binary_search(A[-1] * F[0] + 1)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

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())))
a.sort()
f.sort()
f = f[::-1]
a_sum = a.sum()


def test(x):
    return a_sum - np.minimum(a, x // f).sum() <= k


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

answer = right
print(answer)

Submission status: Accepted

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

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
from itertools import product
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

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


n,k = LI()
a = LI()
f = LI()
a.sort()
f.sort(reverse = True)
ok,ng = 10**12,-1
while ok - ng > 1:
    mid = (ok + ng)//2
    if f_x(mid):
        ok = mid
    else:
        ng = mid
print(ok)

Submission status: Accepted

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

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
from itertools import product
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

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


n,k = LI()
a = LI()
f = LI()
a.sort()
f.sort(reverse = True)
ok = 0
for A,F in zip(a,f):
    ok = max(ok,A*F)
ng = -1
while ok - ng > 1:
    mid = (ok + ng)//2
    if f_x(mid):
        ok = mid
    else:
        ng = mid
print(ok)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import numpy as np
N, K = map(int, input().split())
A = list(map(int, input().split()))
F = list(map(int, input().split()))

A.sort()
F.sort(reverse = True)
sa = sum(A) 
A = np.array(A)
F = np.array(F)

l = -1 
r = A[N-1] * F[0]
while l+1 < r: 
    m = (l + r) //2
    S = sa - np.sum(np.minimum(m // F, A)) 
    if S <= K:
        r = m
    else:
        l = m
         
print(r)

Submission status: Accepted

Solution code:
def is_ok(x):
    result = 0
    for i in range(N):
        t = x // F[i]
        if t < A[i]:
            result += A[i] - 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)

l = -1
r = A[-1] * F[0] + 1

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

Submission status: Accepted

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

t_max=a[0]*F[-1] #絶対True
t_min=-1 #絶対False
while t_max>t_min+1:
    t_mid=(t_max+t_min)//2
    K_temp=np.sum(np.maximum(a-t_mid//F,0))
    if K_temp<=K:
        t_max=t_mid
    else:
        t_min=t_mid
print(t_max)

Submission status: Accepted

Solution code:
import bisect

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)

af = [[0 for i in range(3)] for j in range(n)]

for i in range(n):
    af[i][0] = a[i]*f[i]
    af[i][1] = a[i]
    af[i][2] = f[i]
    
af.sort(reverse=True)

if k == 0:
    print(af[0][0])
    exit()

low = -1
high = af[0][0]+1
tmp = 0

while low+1 < high:
    tmp = 0
    mid = (low + high) //2
    #print(mid)
    
    for i in range(n):
        tmp += max(0,af[i][1] - mid // af[i][2])
    #print(tmp)
    
    if tmp <= k:
        high = mid
    else:
        low = mid
        
print(high)

Submission status: Accepted

Solution code:
class Contest:
    def __init__(self, member_cost,food_cost,k):
        self.member_cost = member_cost
        self.food_cost   = food_cost
        self.max_training_times = k
        
    def canAchieve(self,target):
        sum_training_times = 0
        for i in range(len(self.member_cost)):
            sum_training_times += max(0,self.member_cost[i] - target//self.food_cost[i])

        return  sum_training_times <= self.max_training_times
        


    def bisect(self,begin,end):
        if (end - begin <= 1 ):
            return end
        target = (begin + end)//2
        if self.canAchieve(target):
            return self.bisect(begin,target)

        else:
            return self.bisect(target,end)




def resolve():
    n,k  = map(int,input().split())
    
    member_cost = list(map(int,input().split()))

    food_cost = list(map(int,input().split()))
    member_cost.sort()
    food_cost.sort(reverse=True)
    total_cost = []
    for i in range(len(member_cost)):
        total_cost.append(member_cost[i]*food_cost[i])

    max_total_cost = max(total_cost)
    contest = Contest(member_cost,food_cost,k)
    print(contest.bisect(-1,max_total_cost))
    
resolve()

Submission status: Accepted

Solution code:
import math


def check(A, F, x, N, K):
    for i in range(N):
        if A[i] * F[i] > x:
            k = math.ceil(A[i] - x / F[i])
            K -= k
    if K < 0:
        return False
    else:
        return True


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

    # binary search
    l = 0
    r = max(A) * max(F)
    result = None
    while l <= r:
        # print('l {}, r {}'.format(l, r))
        if l == r:
            result = l
            break
        mid = (l + r) // 2
        if check(A, F, mid, N, K):
            r = mid
        else:
            l = mid + 1

    print(result)


if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
def main():
    N,K=map(int,input().split())
    a_ls=list(map(int,input().split()))
    f_ls=list(map(int,input().split()))
    
    a_ls.sort()
    f_ls.sort()
    f_ls.reverse()
    
    def can_eat_by(x):
        cost_after_training=list(map(lambda item: x//item, f_ls))
        sum=0
        for i in range(N):
            if a_ls[i]>cost_after_training[i]:
                sum+=a_ls[i]-cost_after_training[i]
        return sum<=K
    
    left=-1
    right=10**12
    while left + 1 < right:
        next_x=(right+left)//2
        if can_eat_by(next_x):
            answer=next_x
            right=next_x
        else:
            left=next_x
    print(right)

    '''
    while left + 1 < right:
      mid = (left+right)//2
      if can_eat(mid):
        right = mid
      else:
        left = mid
     
    answer = right
    print(answer)
    '''
    
main()

Submission status: Accepted

Solution code:
def main():
    N,K=map(int,input().split())
    a_ls=list(map(int,input().split()))
    f_ls=list(map(int,input().split()))
    
    a_ls.sort()
    f_ls.sort()
    f_ls.reverse()
    
    def can_eat_by(x):
        cost_after_training=list(map(lambda item: x//item, f_ls))
        sum=0
        for i in range(N):
            if a_ls[i]>cost_after_training[i]:
                sum+=a_ls[i]-cost_after_training[i]
        return sum<=K
    
    left=-1
    right=10**12
    prev_x=-10
    # 二分探索でtest(x)がtrueとなるxの最小値を探索する
    # left = rightとなるまで繰り返す
    while left + 1 < right:
      mid = (left+right)//2
      
      # mid秒で食べられる場合は探索範囲の右端をmidにする
      if can_eat_by(mid):
        right = mid
      # mid秒で食べられない場合は探索範囲の左端をmidにする
      else:
        left = mid
     
    answer = right
    print(answer)

main()

Submission status: Accepted

Solution code:
def main():
	n, k = map(int, input().split())
	*a, = map(int, input().split())
	*f, = map(int, input().split())
	a.sort()
	f.sort(reverse=True)
	prod = sorted([(x * y, y) for x, y in zip(a, f)], reverse=True) + [(0, -1)]
	l = -1
	r = 10 ** 12
	while r - l > 1:
		m = (l + r) // 2
		s = 0
		for p, y in prod:
			if p <= m:
				r = m
				break
			s += 0 - (m - p) // y
			if s > k:
				l = m
				break
	print(r)


if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:

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

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

r = max(a)* max(f)
l = -1

while r-l >1:
    c = (r+l) //2
    ans=0
    for j in range(n):
        ans += max(a[j]- c // f[j] , 0)
    if ans <= k:
        r = c
    else:
        l = c

print(r)

Submission status: Accepted

Solution code:
#!/usr/bin/pypy
import math
import sys
N, K =map(int, raw_input().split())
AN = map(int, raw_input().split())
FN = map(int, raw_input().split())

AN.sort()
FN.sort(reverse=True)

CN=[]
for i in range(N):
    CN.append(AN[i] * FN[i])

s = 0
e = max(CN) + 1
while True:
    m = (s + e) / 2
    tk = K
    for i in xrange(len(CN)):
        if CN[i] > m:
            tk -= math.ceil(1.0 * (CN[i] - m) / FN[i])
            if tk < 0:
                # fail
                if m == s:
                    print str(e)
                    sys.exit(0)
                s = m
                break
    else:
        if m == s:
            print str(0)
            sys.exit(0)
        e = m

Submission status: Accepted

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

start = -1
end = A[-1] * F[0]

def check(now):
    cnt = 0
    for a, f in zip(A, F):
        # cnt += max(0, a-now//f)
        eatable = now//f
        if eatable < a:
            cnt += a - eatable
    # return cnt <= K
    if cnt > K:
        return False
    return True

while end > start + 1:
    now = (start + end) // 2
    if check(now):
        end = now
    else:
        start = now

print(end)