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 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 test(x):
    cost = np.maximum(0, a-x//f).sum()
    return cost <= k


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

print(right)

Submission status: Accepted

Solution code:
import sys
from collections import Counter, deque, defaultdict
from math import factorial
from fractions import Fraction
import heapq, bisect
import math
import itertools
sys.setrecursionlimit(10 ** 5 + 10)
INF = 10**15 +5
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))

n, k = MAP()
a = LIST()
f = LIST()
a = sorted(a, reverse = True)
f = sorted(f)

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

l = -1
r = INF
while l+1 < r:
    mid = (l+r)//2
    if ok(mid):
        r = mid
    else:
        l = mid
print(r)

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[::-1].sort()

sum_A = A.sum()
if sum_A <= K:
    ans = 0
else:
    high = (A * F).max()
    low = 0
    mid = (high + low) // 2
    while low < mid < high:
        if sum_A - np.minimum(A, mid // F).sum() <= K:
            high = mid
        else:
            low = mid
        mid = (high + low) // 2
    ans = high

print(ans)

Submission status: Accepted

Solution code:
from sys import stdout
import heapq
printn = lambda x: stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split()) 
DBG = True  and False
BIG = 999999999
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

def foo(t):
  #ddprint("foo {}".format(t))
  cnt = 0
  for j in range(n):
    v,i = b[j]
    #ddprint("c {} v {} i {}".format(cnt,v,i))
    if v<=t:
      return (cnt<=k)
    d = (v-t+f[i]-1)//f[i]
    cnt += d
    if cnt>k:
      return False
  return (cnt<=k)

n,k = inm()
a = inl()
f = inl()
a.sort()
f.sort(reverse=True)
b = [(f[i]*a[i], i) for i in range(n)]
b.sort(reverse=True)
c = [z[0] for z in b]
mx = max(c)
mn = -1
mid = mx
while mx>mn+1:
  mid = (mx+mn)//2
  if foo(mid):
    #ddprint("mid {} ok".format(mid))
    mx = mid
  else:
    #ddprint("mid {} ng".format(mid))
    mn = mid
print(mx)

Submission status: Accepted

Solution code:
# E - Gluttony

import numpy as np

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

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

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

print(ans)

Submission status: Accepted

Solution code:
# E - Gluttony

import numpy as np

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

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

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

print(ans)

Submission status: Accepted

Solution code:
inpl = lambda: list(map(int,input().split()))
def bisect_left_withkey(a, x, lo=0, hi=None, key=lambda x: x, keyvalue_x=False):
    left = lo
    right = len(a) if hi is None else hi
    kx = key(x) if keyvalue_x else x
    while left + 1 < right:
        new = (left + right)//2
        kn = key(a[new])
        if kx <= kn:
            right = new
        else:
            left = new
    if key(a[left]) == kx:
        return left
    else:
        return right

N, K = inpl()
A = inpl()
F = inpl()
A.sort(reverse=True)
F.sort()
score = [A[i]*F[i] for i in range(N)]

def achievable(m):
    k = 0
    for i in range(N):
        k += max(0, (score[i]-m-1)//F[i] + 1)
        if k > K:
            return False
    return True

M = max(score)
print(bisect_left_withkey(range(M+1), True, key=achievable))

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=1)
su=ok=ng=0
for i in range(n):
  ok=max(ok,a[i]*f[i])
  su+=a[i]
if su<=k:print(0);exit()
while ng+1<ok:
  mid=(ok+ng)//2
  h=0
  for i in range(n):
    r=a[i]-(mid//f[i])
    if (r<0):
      r=0
    h+=r
  if h<=k:ok=mid
  else:ng=mid
print(ok)

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
# E - Gluttony

import numpy as np

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

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

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

print(ans)

Submission status: Accepted

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

def check(A, F, mid, k):
    for i in range(len(A)):
        if A[i] * F[i] > mid:
            x = A[i] - mid // F[i]
            k -= x
        if k < 0:
            return False
    return True



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_s = sorted(A, reverse=True)
    F_s = sorted(F)

    l = -1
    r = 10 ** 13
    while r - l != 1:
        mid = (r + l) // 2
        if check(A_s, F_s, mid, K):
            r = mid
        else:
            l = mid

    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=1)
su=ok=ng=0
for i in range(n):
  ok=max(ok,a[i]*f[i])
  su+=a[i]
if su<=k:print(0);exit()
while ng+1<ok:
  mid=(ok+ng)//2
  h=0
  for i in range(n):
    h+=max(a[i]-(mid//f[i]),0)
  if h<=k:ok=mid
  else:ng=mid
print(ok)

Submission status: Accepted

Solution code:
from numpy import array, int64, minimum

def main():
    N, K, *I = open(0).read().split()
    N, K = map(int, (N, K))

    A, F = array(I[:N], int64), array(I[N:], int64)
    A.sort()
    F.sort()
    F = F[::-1]

    sum_A = A.sum()

    ng, ok = -1, 10 ** 12
    while ng + 1 < ok:
        mid = (ok + ng) // 2
        if (sum_A - minimum(A, mid // F).sum()) <= K:
            ok = mid
        else:
            ng = mid

    print(ok)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N, K  = map(int, input().split())
As = sorted(list(map(int, input().split())))
Fs = sorted(list(map(int, input().split())),reverse=True)
Xs = [a*f for a,f in zip(As,Fs)]
X_M = max(Xs)

def f(x):
    K_tmp = sum([max(0,a-x//f) for a,f in zip(As,Fs)])
    return K_tmp <= K

def  binarySearch(l,r,target):
    while r - l > 1:
        mid = (l+r)//2
        """計算を入れる"""
        # print(mid, guess)
        if f(mid):
            r = mid
        else:
            l = mid
    return r

print(binarySearch(-1,X_M,K))

Submission status: Accepted

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

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

ok = max(A)*max(F)
ng = -1 # -1にしとけば答えが0の時も普通に扱えるな

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

Submission status: Accepted

Solution code:
import numpy as np

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

# Aを昇順、Fを降順に並べ替える
# 消化コストの小さい人に食べにくい食べ物を食べてもらう
A.sort()
F.sort()
F=F[::-1]
sumA = A.sum()

def can_eat(x):
  # 全員がx秒以下で食べられるか調べる
  
  # 食べにくさfの食べ物をx秒以内に食べるための消化コストa'は、
  # a' * f <= x  ->  a' <= x / f
  # a'は整数とすると
  # a' = x // f
  
  # 各消化コストaのうち、a'(x秒以下に収めるための消化コスト)を
  # 超えているものについては、a'に収める
  # こうして、x秒以下に収まっている消化コストの配列を作る
  eat_cost_for_x = np.minimum(A, x // F)
  
  # 元の消化コストの合計と、
  # x秒以下に収まっている消化コスト（eat_cost_for_x）の合計を比較し、
  # 修行できる回数(K)以内の差であれば、全員x秒以下で食べられる
  return sumA - eat_cost_for_x.sum() <= K


# 不可能目標（最小でも0秒のため）
left = -1 
# 可能目標 (a <= 10^6, f <= 10^6 なので、a*f <= 10^12)
right = 10**12

# 二分探索でtest(x)がtrueとなるxの最小値を探索する
# left = rightとなるまで繰り返す
while left + 1 < right:
  mid = (left+right)//2
  
  # mid秒で食べられる場合は探索範囲の右端をmidにする
  if can_eat(mid):
    right = mid
  # mid秒で食べられない場合は探索範囲の左端をmidにする
  else:
    left = mid
 
answer = right
print(answer)

Submission status: Accepted

Solution code:
import numpy as np
n, k = map(int,input().split())
a = np.array(input().split(), np.int64)
f = np.array(input().split(), np.int64)

a.sort()
f.sort()
f=f[::-1]
a_sum = a.sum()
low, high = -1, max(a)*max(f)
while low + 1 < high:
  mid = (low + high) // 2
  if np.minimum(a, mid // f).sum() >= a_sum - k:
    high = mid
  else:
    low = mid
print(high)

Submission status: Accepted

Solution code:
from numpy import array, int64, minimum
from sys import stdin

def main():
    input = stdin.buffer.readline

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

    A, F = array(input().split(), int64), array(input().split(), int64)
    A.sort()
    F.sort()
    F = F[::-1]

    sum_A = A.sum()

    ng, ok = -1, 10 ** 12
    while ng + 1 < ok:
        mid = (ok + ng) // 2
        if (sum_A - minimum(A, mid // F).sum()) <= K:
            ok = mid
        else:
            ng = mid

    print(ok)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from numpy import array, int64, minimum

def main():
    N, K, *I = map(int, open(0).read().split())

    A, F = array(I[:N], int64), array(I[N:], int64)
    A.sort()
    F.sort()
    F = F[::-1]

    sum_A = A.sum()

    ng, ok = -1, 10 ** 12
    while ng + 1 < ok:
        mid = (ok + ng) // 2
        if (sum_A - minimum(A, mid // F).sum()) <= K:
            ok = mid
        else:
            ng = mid

    print(ok)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import numpy as np

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

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


def ok(x):
    return np.clip(a - x // f, 0, None).sum() <= k


l, r = 0, 10 ** 12

while l <= r:
    mid = (l + r) // 2
    if ok(mid):
        r = mid - 1
    else:
        l = mid + 1

print(l)

Submission status: Accepted

Solution code:
import numpy as np

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

Asum = sum(A)

Asort = np.array(sorted(A))
Fsort = np.array(sorted(F,reverse=True))

def test(x):
    res = np.maximum(0,Asort-x//Fsort).sum()
    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: Accepted

Solution code:
import math
(n,k),a,f = [list(map(int, s.split())) for s in open(0)]

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

low = 0
high = 0
for x, y in zip(a,f):
    high = max(high, x*y)

while high != low:
    test = int((high + low) // 2)
    tmp = 0
    for x, y in zip(a,f):
        tmp += max(0, x - math.floor(test / y))
        if tmp > k:
            low = test + 1
            break
    else:
        high = test
print(high)

Submission status: Accepted

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
import numpy as np

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

	A = np.array(A)
	F = np.array(F)
	time = A*F
	# print(F)
	# print(time)
	sum_A = A.sum()

	def is_ok(x):  # 時間をx以下にできるか？
		return sum_A - np.minimum(A,x//F).sum() <= K

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

	print(max_)


if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
(n,k),a,f = [list(map(int, s.split())) for s in open(0)]

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

low = 0
high = 0
for x, y in zip(a,f):
    high = max(high, x*y)

while high != low:
    test = int((high + low) // 2)
    tmp = 0
    for x, y in zip(a,f):
        tmp += max(0, x - int(test / y))
        if tmp > k:
            low = test + 1
            break
    else:
        high = test
print(high)

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
A = list(map(int,input().split()))
F = list(map(int,input().split()))
import numpy as np
s_A = sum(A)
if s_A<=K:
  print(0)

else:
  A.sort()
  F.sort(reverse=True)
  A = np.array(A)
  F = np.array(F)
  mi=0
  ma=max(F)*max(A)
  while mi+1<ma:
    mid = (mi+ma)//2
    if s_A-np.minimum(A,mid//F).sum()<=K:
      ma=mid
    else:
      mi=mid

  print(ma)

Submission status: Accepted

Solution code:
inpl = lambda: list(map(int,input().split()))
def bisect_left_withkey(a, x, lo=0, hi=None, key=lambda x: x, keyvalue_x=False):
    left = lo
    right = len(a) if hi is None else hi
    kx = key(x) if keyvalue_x else x
    while left + 1 < right:
        new = (left + right)//2
        kn = key(a[new])
        if kx <= kn:
            right = new
        else:
            left = new
    if key(a[left]) == kx:
        return left
    else:
        return right

N, K = inpl()
A = inpl()
F = inpl()
A.sort()
F.sort(reverse=True)
score = [A[i]*F[i] for i in range(N)]

def achievable(m):
    k = 0
    for i in range(N):
        k += max(0, (score[i]-m-1)//F[i] + 1)
        if k > K:
            return False
    return True

M = max(score)
print(bisect_left_withkey(range(M+1), True, key=achievable))

Submission status: Accepted

Solution code:
import sys


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    n, k = list(map(int, input().rstrip('\n').split()))
    a = list(map(int, input().rstrip('\n').split()))
    f = list(map(int, input().rstrip('\n').split()))
    a.sort()
    f.sort(reverse=True)
    left = -1
    right = 10 ** 13
    while right - left > 1:
        mid = (left + right) // 2
        count = 0
        for av, fv in zip(a, f):
            count += max(0, av - (mid // fv))
        if count <= k:
            right = mid
        else:
            left = mid
    print(right)


if __name__ == '__main__':
    solve()

Submission status: Accepted

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)
    return temp <= K
 
 
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: Accepted

Solution code:
import math
(n,k),a,f = [list(map(int, s.split())) for s in open(0)]

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

low = 0
high = 0
for x, y in zip(a,f):
    high = max(high, x*y)

while high != low:
    test = int((high + low) // 2)
    tmp = 0
    for x, y in zip(a,f):
        tmp += max(0, x - math.floor(test / y))
        if tmp > k:
            low = test + 1
            break
    else:
        high = test
print(high)

Submission status: Accepted

Solution code:
import numpy as np

n, k = map(int, input().split())
a = np.sort(np.array(input().split(), dtype=np.int))
f = np.sort(np.array(input().split(), dtype=np.int))
time = f * a[::-1]

sup = time.max()
inf = 0
while sup > inf:
  x = (sup + inf) // 2
  train = ((np.maximum(time - x, 0) + f - 1) // f).sum()
  if k < train:
    inf = x + 1
  else:
    sup = x
print(sup)

Submission status: Accepted

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):
    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:
            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: Accepted

Solution code:
import math

def read():
    N, K = list(map(int, input().strip().split()))
    A = list(map(int, input().strip().split()))
    F = list(map(int, input().strip().split()))
    return N, K, A, F

def solve(N, K, A, F):
    A = list(sorted(A))
    F = list(reversed(sorted(F)))
    mul = [A[i] * F[i] for i in range(N)]
    smul = list(sorted(mul)) + [9999999999]
    
    def f(x):
        k = 0
        for i in range(N):
            if x < mul[i]:
                k += math.ceil((mul[i] - x) / F[i])
        return k
    
    lb = 0
    ub = 10 ** 12
    while lb < ub:
        x = lb + (ub - lb) // 2
        if f(x) > K:
            # K回の修行では足りない
            lb = x+1
        else:
            ub = x
    return lb

if __name__ == '__main__':
    inputs = read()
    print("%d" % solve(*inputs))

Submission status: Accepted

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

A=np.array(A)
F=np.array(F)

def judge(x):
    over=np.maximum(A*F-x,0)
    shug=-(-over//F).sum()
    return shug<=K

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: Accepted

Solution code:
#!/usr/bin/env python3
import sys
input = lambda: sys.stdin.readline()[:-1]
sys.setrecursionlimit(10**8)
inf = float('inf')
mod = 10**9+7

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=0
right=10**12+1
ok=inf
while left<right:
    mid=(left+right)//2
    # print(mid)
    tmp=0
    for i in range(n):
        tmp+=max(0,A[i]-mid//F[i])
    if tmp>k:
        left=mid+1
    else:
        right=mid
        ok=min(ok,mid)
print(ok)

Submission status: Accepted

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 False
        
        if cnt <= k:
            return True
        else:
            return False





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

    
            
    

    

    

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N, K = [int(x) for x in input().split()]
A = sorted([int(x) for x in input().split()])
F = sorted([int(x) for x in input().split()], reverse=True)
lb = 0
ub = 10 ** 12
def isPossible(M):
    cnt = 0
    # a = 4 , f = 5 のとき a*f = 20
    # M = 30 => そのままでOK
    # M = 9 => (20-9+4)//5
    for a, f in zip(A, F):
        if (M >= a*f): continue
        cnt += (a*f - M + (f-1)) // f
    return cnt <= K

for i in range(100):
    mid = (lb + ub) // 2
    if (isPossible(mid)):
        ub = mid
    else:
        lb = mid
print(ub)

Submission status: Accepted

Solution code:
import sys,collections as cl,bisect as bs,heapq as hq
sys.setrecursionlimit(100000)
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

def prime_decomposition(n): #素因数分解
  i = 2
  table = []
  while i * i <= n:
    while n % i == 0:
      n /= i
      table.append(i)
    i += 1
  if n > 1:
    table.append(int(n))
  return table

def make_divisors(n): #約数列挙
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors


def ok(x,p):
    kkk = 0
    for i in range(len(x)):
        kkk += max(0,-(-(x[i][0] - p) // x[i][2]))
    return kkk


n,k = m()
a = l()

f = l()

for i in range(n):
    a[i]


a.sort(reverse = True)

f.sort()
co = 0

d = []

for i in range(n):
    d.append([a[i]*f[i],a[i],f[i]])

d.sort(reverse = True)



ll = 0

rr = d[0][0] 


while True:
    mid = (rr+ll)//2

    if rr == mid:
        break

    if ok(d,mid) <= k:
        rr = mid
    else:
        ll = mid+1

print(ll)

Submission status: Accepted

Solution code:
import numpy as np

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

  A.sort()
  F.sort()
  F=F[::-1]
  a_sum = A.sum()
  low, high = -1, 10**13

  while low + 1 < high:
      mid = (low + high) // 2
      if np.minimum(A, mid // F).sum() >= a_sum - K:
          high = mid
      else:
          low = mid
  return high

print(solve())

Submission status: Accepted

Solution code:
#!/usr/bin/env python
import sys
from math import ceil

_HO = 10**12 + 1

def binary_search(lo=0,ho=_HO):
    if ho-lo==1: return lo

    mid = lo + (ho-lo-1)//2
    if check(mid):
        return binary_search(lo=lo,ho=mid+1)
    else:
        return binary_search(lo=mid+1,ho=ho)

def check(x):
    global k, a, f

    s = 0
    for ai, fi in zip(a,f):
        af = ai * fi
        if af<=x: continue
        s += ceil((af-x)/fi)
        if s>k: return False
    #
    return True

n,k = [ int(x) for x in sys.stdin.readline().strip().split() ]
a = [ int(x) for x in sys.stdin.readline().strip().split() ]
f = [ int(x) for x in sys.stdin.readline().strip().split() ]

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

print(binary_search())

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N, K = map(int, input().split())
a = list(map(int, input().split()))
f = list(map(int, input().split()))
a.sort()
f.sort(reverse = True)
res = 0
l = 0
r = 10 ** 12
m = int((l + r) / 2)
c = 0
if sum(a) <= K:
  print(0)
  exit(0)
def check(x):
  k = K + 0
  for i in range(N):
    if a[i] * f[i] > x:
      k -= abs((x - a[i] * f[i]) // f[i])
    if k < 0:
      return False
  return True
while c <= 64:
  m = int((l + r) / 2)
  if check(m) == True:
    r = m
  else:
    l = m
  c += 1
if check(m + 1): print(m + 1)
elif check(max(0, m - 1)): print(m - 1)
else: print(m)

Submission status: Accepted

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 True:
        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: Accepted

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

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


def judge(s):
    global N, K
    ksum = 0
    for i in range(N):
        ksum += max(0, -(-(A[i] * F[i] - s) // F[i]))
    if ksum <= K:
        return True
    else:
        return False

lb = -1
ub = 10**13
while lb + 1 < ub:
    mid = (lb + ub) // 2
    if judge(mid):
        ub = mid
    else:
        lb = mid

print(ub)

Submission status: Accepted

Solution code:
import numpy as np

def test(x, A, F):
	return np.clip(A - x // F, 0, None).sum() <= K

if __name__ == "__main__":
	N, K = map(int, input().split())
	A = np.array([int(a) for a in input().split()])
	F = np.array([int(a) for a in input().split()])
	A = np.sort(A)
	F = np.sort(F)[::-1]
	left = -1
	right = 10**12 + 1
	while left + 1 < right:
		mid = (left + right) // 2
		if test(mid, A, F):
			right = mid
		else:
			left = mid
	ans = right
	print(ans)

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
N,K=map(int,input().split())
A=list(map(int,input().split()))
A=sorted(A)
F=list(map(int,input().split()))
F=sorted(F,reverse=True)

def is_ok(b):
    k=0
    for a,f in zip(A,F):
        if a>b//f:
            k+=a-(b//f)
            if k>K:
                return False
    return True

ok=10**12+1
ng=-1
while ok-ng>1:
    m=(ok+ng)//2
    if is_ok(m):
        ok=m
    else:
        ng=m

print(ok)

Submission status: Accepted

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

def is_ok(b):
    m=0
    for p,q in zip(a,f):
        if p>b//q:
            m+=p-(b//q)
            if m>k:
                return False
    return True

ok=10**12+1
ng=-1
while ok-ng>1:
    m=(ok+ng)//2
    if is_ok(m):
        ok=m
    else:
        ng=m

print(ok)

Submission status: Accepted

Solution code:
import numpy as np

N, K = map(int, input().split())
A_lis = list(map(int, input().split()))
F_lis = list(map(int, input().split()))
A_lis = np.sort(A_lis)[::-1]
F_lis = np.sort(F_lis)

if A_lis.sum() <= K:
    print(0)
    exit()
if K == 0:
    print((A_lis * F_lis).max())

high = (A_lis * F_lis).max()
low = 0

while high > low + 1:
    mid = (high + low) // 2
    if (A_lis - np.minimum(A_lis, (mid // F_lis))).sum() <= K: #可能
        high = mid
    else:
        low = mid
print(high)