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:
N, K = map(int, input().split())
A = list(map(int, input().split()))
F = list(map(int, input().split()))
A.sort()
F.sort(reverse=True)
end = A[-1] * F[0] + 1
start = -1


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

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


print(calc())

Submission status: Accepted

Solution code:
import sys

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

Submission status: Accepted

Solution code:
def solve():
    N, K = map(int, input().split())
    As = list(map(int, input().split()))
    Fs = list(map(int, input().split()))

    As.sort()
    Fs.sort(reverse=True)

    def isOK(score):
        d = 0
        for A, F in zip(As, Fs):
            if A*F > score:
                d += -(-(A*F-score) // F)
        return d <= K

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

    print(ok)


solve()

Submission status: Accepted

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
n,k = map(int,input().split())
a = list(map(int,input().split()))
f = list(map(int,input().split()))
l = -1
r = 10**12

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

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

print(r)

Submission status: Accepted

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

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

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

    # 時間tで感触できるか
    def can_complete(t):
        return np.maximum(0, A-t//F).sum() <= K

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

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

if __name__ == '__main__':
    resolve()

Submission status: Accepted

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

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


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


ub = 10**12
lb = -1

while lb + 1 < ub:
    x = (ub+lb)/2
    if judge(x):
        ub = x
    else:
        lb = x

print(int(ub))

Submission status: Accepted

Solution code:
def check(mid):
	val = 0
	for i in c:
		if(i[0]*i[1] > mid):
			val += i[0] - (mid//i[1])
	return val <= k

def bs():
	l = 0
	r = 1e18
	while(l <= r):
		mid = (l+r)//2
		if(check(mid)):
			r = mid-1
		else:
			l = mid+1
	return r+1

n,k = map(int,input().split())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
a.sort()
b.sort(reverse = True)
c = [[a[i],b[i]] for i in range(n)]
print(int(bs()))

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc144/tasks/abc144_e


# 修行を行わないときに最適なのは両方を逆順でソートしておくこと
# そうしたときになるべく食べ物のコストの大きい方から修行していったほうが最適なので
# greedyにKをみたすまで引いてあげる

# 求めたいのは最大値！
# 最小はxにできると仮定してみる？
# 答えはxより小さくなる→greedyに(Ai-a)Fi<xして判定すれば良い

import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def read_ints():
    return list(map(int, read().split()))


N, K = read_ints()
A = read_ints()
F = read_ints()
A.sort()  # 前からFの大きい順に対処していく人になっている
F.sort(reverse=True)
# print(A)
# print([x * y for x, y in zip(A, F)])  # ここから崩すことができるポイントを探せる


def is_ok(x, K):
    for i in range(N):
        if A[i] * F[i] <= x:
            continue
        a = A[i] - (x // F[i])  # Kから使うべき個数
        K -= a
        if K < 0:
            return False
    return K > -1


def meguru_bisect(ng, ok):
    '''
    define is_okと
    初期値のng,okを受け取り,is_okを満たす最小(最大)のokを返す
    ng ok は  とり得る最小の値-1 とり得る最大の値+1
    最大最小が逆の場合はよしなにひっくり返す
    '''
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if is_ok(mid, K):
            ok = mid
        else:
            ng = mid
    return ok


print(meguru_bisect(-1, 10**12 + 1))

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc144/tasks/abc144_e


# 修行を行わないときに最適なのは両方を逆順でソートしておくこと
# そうしたときになるべく食べ物のコストの大きい方から修行していったほうが最適なので
# greedyにKをみたすまで引いてあげる

# 求めたいのは最大値！
# 最小はxにできると仮定してみる？
# 答えはxより小さくなる→greedyに(Ai-a)Fi<xして判定すれば良い

import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def read_ints():
    return list(map(int, read().split()))


N, K = read_ints()
A = read_ints()
F = read_ints()
A.sort()  # 前からFの大きい順に対処していく人になっている
F.sort(reverse=True)
# print(A)
# print([x * y for x, y in zip(A, F)])  # ここから崩すことができるポイントを探せる

from math import ceil


def is_ok(x, K):
    for i in range(N):
        if A[i] * F[i] <= x:
            continue
        a = ceil(A[i] - x / F[i])  # Kから使うべき個数
        K -= a
        if K < 0:
            return False
    return K > -1


def meguru_bisect(ng, ok):
    '''
    define is_okと
    初期値のng,okを受け取り,is_okを満たす最小(最大)のokを返す
    ng ok は  とり得る最小の値-1 とり得る最大の値+1
    最大最小が逆の場合はよしなにひっくり返す
    '''
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if is_ok(mid, K):
            ok = mid
        else:
            ng = mid
    return ok


print(meguru_bisect(-1, 10**12 + 1))

Submission status: Accepted

Solution code:
"""

AtCoder Beginner Contest 144  E - Gluttony


愚直解
・修行の順序は結果に影響しないから、修行を誰に割り振るか：N^K
・メンバーN人をどの問題に当てるか（N人の並べ方）：N!
-> N^K * N! 
間に合わない。

完食にかかる時間のうち最大値がチーム全体の成績なので、
・消化コストAiを修行で下げる
・消化コストAiの大きい人に、食べにくさFiの小さい食べ物を割り当てる
のが良さそう

最大値の最小化、なので、二分探索が使えそうな気もする。

A,F <= 10^6
かかる時間を X 以下にできるか、を考える。
・消化コストが大きい人に、食べにくさが小さい問題を当てるようにする
・Ai * Fi > Xであれば、(Ai - m) * Fi <= X となるような最小のmをカウントする
全メンバーに対しこれを数え上げた時に、
mの合計 > K
であれば、X以下になるように修行することができない（K回までしか修行できず、回数が足りない）ので、最大値の最小はXより上
mの合計 <= K
であれば、X以下になるように修行できるので、最大値の最小はX以下

A*F <= 10^12 までなので、40~50程度繰り返せば行けそう
"""
import math

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

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

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

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

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

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

Submission status: Accepted

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

n,k=map(int,input().split())
a=sorted(map(int,input().split()))
f=sorted(map(int,input().split()),reverse=True)

ng,ok=-1,10**18
while(ok-ng>1):
    mid=(ok+ng)//2
    if isok(mid):
        ok=mid
    else:
        ng=mid
print(ok)

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    n, k = list(map(int, readline().split()))
    a = list(map(int, readline().split()))
    f = list(map(int, readline().split()))

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

    x = [p * q for p, q in zip(a, f)]
    mx = max(x)
    ng = -1
    ok = mx
    import math

    while abs(ok - ng) > 1:
        mid = (ng + ok) // 2
        rem = k
        for p, q in zip(a, f):
            r = math.floor(mid / q)
            h = max(0, p - r)
            rem -= h
        if rem >= 0:
            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 = np.array(list(map(int,input().split())))
f = np.array(list(map(int,input().split())))

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

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

def nibutan(low,hi):
    while True:
        ave = (low+hi)//2
        #ここの条件式を問題文に合わせる
        if test(ave):
            hi = ave
        else:
            low = ave
        if hi - low == 1:
            break
    li = [low,hi]
    return li

li = nibutan(-1,10**12)

print(li[1])

Submission status: Accepted

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

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)
c = [(i*j,j) for i,j in zip(a,f)]
m = max(c)

def is_ok(arg):
    # 条件を満たすかどうか？問題ごとに定義
    chk = 0
    for i,j in c:
      chk += math.ceil(max(0,(i-arg))/j)
    return chk <= k


def bisect_ok(ng, ok):
    '''
    初期値のng,okを受け取り,is_okを満たす最小(最大)のokを返す
    まずis_okを定義
    ng = 最小の値-1 ok = 最大の値+1 で最小
    最大最小が逆の場合はng ok をひっくり返す
    '''
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if is_ok(mid):
            ok = mid
        else:
            ng = mid
    return ok
  
print(bisect_ok(-1,m[0]+1))

Submission status: Accepted

Solution code:
import numpy as np
N, K = map(int, input().split())
A = np.array(tuple(map(int, input().split())))
F = np.array(tuple(map(int, input().split())))

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

Submission status: Accepted

Solution code:
#k回消化コストを-1できる

n,k=map(int,input().split())
#消化コスト
a=list(map(int,input().split()))
a.sort()
#食べにくさ
f=list(map(int,input().split()))
f.sort(reverse=True)

#食べやすいものを消化コストが高い人
#食べにくいものを消化コストが低い人にしたほうがいい
#kをどこで減らすかは2部探索
#a-ans//f の和がk以下で、最小のans

ll=-1
rr=10**18

result=10**18
while ll+1<rr:
    ans=(rr+ll)//2
    
    cnt=0
    for i in range(n):
        cnt+=max(0,a[i]-ans//f[i])
    if cnt<=k:
        rr=ans
    else:
        ll=ans
#ansが小さくなると、cntが大きくなる



print(rr)

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

hq = []

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

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

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

Submission status: Accepted

Solution code:
import numpy as np
def bin_search(left, right, check):
    while left + 1 < right:
        middle = (left + right) >> 1
        if check(middle):
            right = middle
        else:
            left = middle
    return right

def make_check(A, F, Z, K):
    def check(m):
        return np.maximum(A - m // F, Z).sum() <= K
    return check

N, K = map(int, input().split())
A = np.array(input().split(), dtype=np.int32)
F = np.array(input().split(), dtype=np.int32)
Z = np.zeros((N,), dtype=np.int32)
A.sort()
F = F[np.argsort(-F)]
check = make_check(A, F, Z, K)

print(bin_search(-1, 10 ** 12, check))

Submission status: Accepted

Solution code:
import numpy as np
def bin_search(left, right, check):
    while left + 1 < right:
        middle = (left + right) >> 1
        if check(middle):
            right = middle
        else:
            left = middle
    return right

def check(m):
    return np.maximum(A - m // F, Z).sum() <= K

N, K = map(int, input().split())
A = np.array(input().split(), dtype=np.int32)
F = np.array(input().split(), dtype=np.int32)
Z = np.zeros((N,), dtype=np.int32)
A.sort()
F = F[np.argsort(-F)]

print(bin_search(-1, 10 ** 12, 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 = sorted(A)
F = sorted(F, reverse=True)

l = -1 # 絶対にfalse
r = 10**12+5
while (l+1<r):
  c = (l+r)//2
  s = 0
  for i in range(N):
    s += max(0, A[i]-(c//F[i]))
  if s <= K:
    r = c
  else:
    l = c

print(r)

Submission status: Accepted

Solution code:
import math

def solve(x):
    y = 0
    for i in range(n):
        if a[i] >= x / f[i]:
            y += math.ceil(a[i] - x / f[i])
    if y <= k:
        return True
    else:
        return False

def binary_search(c1, c2):
    m = (c1 + c2 + 1) // 2
    if abs(c1 - c2) <= 1:
        return m
    else:
        if solve(m):
            c1 = m
        else:
            c2 = m
        return binary_search(c1, c2)

n, k = map(int, input().split())
a = list(map(int, input().split()))
f = list(map(int, input().split()))
a.sort()
f.sort(reverse = True)
M = 0
for i in range(n):
    M = max(M, a[i] * f[i])
ans = binary_search(M, -1)
print(ans)

Submission status: Accepted

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

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

n,k = map(int,input().split())
a = list(map(int,input().split()))
f = list(map(int,input().split()))
a.sort()
f.sort(reverse = True)
print(bisect(-1,10**12))

Submission status: Accepted

Solution code:
import sys
N,K=map(int,input().split())
alist=list(map(int,input().split()))
flist=list(map(int,input().split()))
alist.sort()
flist.sort(reverse=True)
#print(alist)
#print(flist)

def check(m):
  cnt=0
  for i in range(N):
    if alist[i]*flist[i]>m:
      cnt+=-(-(alist[i]*flist[i]-m)//flist[i])
  
  #print(m,cnt,K)
  if cnt<=K:
    return True
  else:
    return False

if sum(alist)<=K:
  print(0)
  sys.exit(0)

baseline=0
for i in range(N):
  baseline=max(baseline,alist[i]*flist[i])
#print(baseline)

l,r=0,baseline
while l<=r:
  mid=(l+r)//2
  #print(l,mid,r)
  if not check(mid-1) and check(mid):
    print(mid)
    break
  elif not check(mid):
    l=mid+1
  else:
    r=mid-1

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(reverse = True)
f.sort()
top = 10**13
bot = -1
def ok(x):
    res = 0
    for i in range(n):
        res += max(0,a[i] - (x//f[i]))
    return res <=k
while top - bot > 1:
    mid = (top + bot) //2
    if ok(mid):top = mid
    else:bot = mid
print(top)

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math

    #inf = 10**17
    #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)

    def check(mid, k):
        for i in range(n):
            if a[i]*f[i] <= mid:
                continue
            k -= a[i] - mid // f[i]
            if k < 0:
                return False
        return True

    ng = -1
    ok = 10**12
    while ok - ng > 1:
        mid = (ok + ng) // 2
        if check(mid, 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=np.array(input().split(),dtype=np.int64)
f=np.array(input().split(),dtype=np.int64)

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

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

while m+1<M:
    pos=(m+M)//2
    if safe(pos):
        M=pos
    else:
        m=pos
print(M)

Submission status: Accepted

Solution code:
def f(point):
    cnt = 0
    for i in range(N):
        a, f = A[i], F[i]
        cnt += max(0, a - point//f)
    return cnt <= 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 = 10**12
while (r-l) > 1:
    mid = (r+l)//2
    if f(mid):
        r = mid
    else:
        l = mid
print(r)

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

Submission status: Accepted

Solution code:
import math
ceil = math.ceil
def isok(x):
    syugyo = 0##全員の時間がx以下を達成するための修行回数
    for i in range(n):
        syugyo += max(0,  ceil(( A[i]*F[i]-x )/F[i])  )
    return syugyo>kai
def bisect():
    ok = -1
    ng = 10**12+1 ##最小コストの最大値
    x = (ok+ng)//2
    while ng-ok>1:
        if isok(x):
            ok = x
        else:
            ng = x
        x = (ok+ng)//2
    return ok+1 ##一番右のTrueのindex  Trueの個数はok+1こ


n,kai = map(int,input().split())
A = list(map(int,input().split()))
F = list(map(int,input().split()))
F.sort()
A.sort(reverse=True)
print(bisect())

Submission status: Accepted

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

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

l = 0
r = 10**12 + 100

def solve(num):
	B = num // F
	tmp = np.sum(np.maximum(0, A - B))
	if tmp <= K:
		return 1
	else:
		return 0

while r - l > 1:
	mid = (l + r) // 2
	if solve(mid):
		r = mid
	else:
		l = mid

if solve(l):
	print(l)
else:
	print(r)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import numpy as np
n,k=map(int,readline().split())
a=np.array(readline().split(),np.int64)
f=np.array(readline().split(),np.int64)
a.sort()
f.sort()
f=f[::-1]

s=-1
e=10**12
while s+1<e:
    mid=(s+e)//2
    if a.sum()- np.minimum(a,mid//f).sum() <=k:
        e=mid
    else:
        s=mid
print(e)

Submission status: Accepted

Solution code:


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

    A.sort()
    F.sort(reverse = True)
    AF  = list(zip(A,F))

    if sum(A)<=K:
        print(0)
        return
    l = 0
    r = max([i*j for i,j in AF])
    center =0
    while l < r-1:

        center = (l+r)//2
        score =sum([max(0,a-center//f) for a,f in AF])
        
        if score > K:
            l = center
        else:
            r = center

    print(r)





if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
#ABC144-E Gluttony
"""
消化コストの小さい人から食べにくさの大きいものを割り当てるのは確定。
問題は全員のコスト*食べにくさ　の合計ではなく、最もその値が大きい人の
スコアを最小化することである。

最大値の最小化は、最大値を決め打って二分探索。
コストの昇順と食べにくさの降順を対応させ、食べにくさ*need<=決め打った最大値
となるようなneedを求め、k -= max(0,-need+コスト)していく。
kが0未満になってしまった場合はその決め打った最大値は達成できない。
"""
import sys
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0

n,k = map(int,readline().split())
lsta = list(map(int,readline().split()))
lstf = list(map(int,readline().split()))

lsta.sort()
lstf.sort(reverse=True)
def func(mid,k):
    for i in range(n):
        need = mid//lstf[i] #need以下にしないといけない
        k -= max(0,lsta[i]-need)
        if k < 0:
            return 0
    return 1

def binary_search(): #2分探索
    ok = 10**20
    ng = -1
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if func(mid,k):
            ok = mid
        else:
            ng = mid

    return ok

print(binary_search())

Submission status: Accepted

Solution code:
def is_ok(a_list, f_list, score, k):
    cnt = 0
    for i in range(len(a_list)):
        target = score // f_list[i]
        cnt += max(0, a_list[i] - target)
        if cnt > k:
            return False
    return True


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

a_list.sort()
f_list.sort()
f_list.reverse()

ok, ng = 10 ** 12, -1
while ok - ng > 1:
    mid = (ok + ng) // 2
    if is_ok(a_list, f_list, mid, k):
        ok = mid
    else:
        ng = mid
print(ok)

Submission status: Accepted

Solution code:
# わからんだろこれ 降順ソート*昇順ソートからの発想が浮かばず
n, k = map(int, input().split())
a = sorted(list(map(int, input().split())))
b = sorted(list(map(int, input().split())), reverse=True)
l, r = -1, 10**12 + 1  # ちゃんと「取りうることがないもののうち最大値」「取りうることのない最小値」でやる.....

while r - l > 1:
    mid = (r + l) // 2  # 最大値これをめざす
    cur = 0
    for i in range(n):
        if a[i] * b[i] <= mid:
            # Kを使う必要がない
            pass
        else:
            # Kからどんくらい使うか これむずくない？
            cur += a[i] - mid // b[i]
    if cur > k:
        l = mid
    else:
        r = mid
print(r)

Submission status: Accepted

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

def ok(c):
    s = 0
    for i in range(N):
        s += max(0, A[i] - c // F[i])
    return s <= K

A.sort()
F.sort(reverse=True)
l, r = -1, 10 ** 12
while l + 1 < r:
    c = (l + r) // 2
    if ok(c):
        r = c
    else:
        l = c
print(r)

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(reverse=True)
F.sort()
U = 10**12
L = -1
while U - L > 1:
    x = (U+L)//2
    cnt = 0
    for i in range(N):
        if x//F[i] < A[i]:
            cnt += A[i] - x//F[i]
    if cnt > K:
        L = x
    else:
        U = x
print(U)

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)

hi = 10**18
lo = -1

while hi - lo > 1:
    mid = (hi + lo) // 2
    tr = 0
    for i in range(N):
        if A[i] * F[i] > mid:
            tr += A[i] - mid // F[i]
    if tr > K:
        lo = mid
    else:
        hi = mid

print(hi)

Submission status: Accepted

Solution code:
import numpy as np

def solve(n, k, aaa, fff):
    aaa = np.sort(aaa)
    fff = np.sort(fff)[::-1]

    l = -1
    r = 1e12
    while l+1 < r:
        c = (l+r)//2
        s = np.clip(aaa - c//fff, 0, None).sum()
        if s <= k:
            r = c
        else:
            l = c
    return int(r)


n, k = map(int, input().split())
aaa = np.array(list(map(int, input().split())), dtype=np.int64)
fff = np.array(list(map(int, input().split())), dtype=np.int64)

print(solve(n, k, aaa, fff))

Submission status: Accepted

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

def main():
    N,K = map(int,input().split())
    a = list(map(int,input().split()))
    f = list(map(int,input().split()))
    
    a.sort()
    f.sort(reverse=True)
    
    l,r = -1,max(a)*max(f)+1
    
    while r-l>1:
        mid = (r+l)//2
        count = 0
        for cost,dif in zip(a,f):
            if mid >= cost*dif:
                continue
            rest = cost*dif-mid
            count += -(-rest//dif)
        if count <= K:
            r = mid
        else:
            l = mid
            
    print(r)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
mod = 10 ** 9 + 7
from collections import deque
import heapq


def iip(listed):
    ret = [int(i) for i in input().split()]
    if len(ret) == 1 and not listed:
        return ret[0]
    return ret


def main():
    r = solve()
    print(r)


def solve():
    N, K = iip(False)
    A = iip(True)
    F = iip(True)

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

    l = -1
    r = 10**12
    while r - l > 1:

        x = (l+r)//2
        nk = 0

        for a, f in zip(A, F):
            lima = x // f
            #print(lima, a)
            syugyou = a - lima
            #print(syugyou)
            if x <= 10:
                #print(x, a, f, lima, syugyou)
                pass
            nk += max(0, syugyou)


        if nk > K:
            l = x
        else:
            r = x

    #print(l, r)

    return r


#####################################################ライブラリ集ここから

def split_print_space(s):
    print(" ".join([str(i) for i in s]))


def split_print_enter(s):
    print("\n".join([str(i) for i in s]))


def koenai_saidai_x_index(sorted_list, n):
    l = 0
    r = len(sorted_list)
    if len(sorted_list) == 0:
        return False
    if sorted_list[0] > n:
        return False

    while r - l > 1:
        x = (l + r) // 2
        if sorted_list[x] == n:
            return x
        elif sorted_list[x] > n:
            r = x
        else:
            l = x
    return l


def searchsorted(sorted_list, n, side):
    if side not in ["right", "left"]:
        raise Exception("sideはrightかleftで指定してください")

    l = 0
    r = len(sorted_list)

    if n > sorted_list[-1]:
        # print(sorted_list)
        return len(sorted_list)
    if n < sorted_list[0]:
        return 0

    while r - l > 1:
        x = (l + r) // 2
        if sorted_list[x] > n:
            r = x
        elif sorted_list[x] < n:
            l = x
        else:
            if side == "left":
                r = x
            elif side == "right":
                l = x

    if side == "left":
        if sorted_list[l] == n:
            return r - 1
        else:
            return r

    if side == "right":
        if sorted_list[l] == n:
            return l + 1
        else:
            return l


def soinsuu_bunkai(n):
    ret = []
    for i in range(2, int(n ** 0.5) + 1):
        while n % i == 0:
            n //= i
            ret.append(i)
        if i > n:
            break
    if n != 1:
        ret.append(n)
    return ret


def conbination(n, r, mod, test=False):
    if n <= 0:
        return 0
    if r == 0:
        return 1
    if r < 0:
        return 0
    if r == 1:
        return n
    ret = 1
    for i in range(n - r + 1, n + 1):
        ret *= i
        ret = ret % mod

    bunbo = 1
    for i in range(1, r + 1):
        bunbo *= i
        bunbo = bunbo % mod

    ret = (ret * inv(bunbo, mod)) % mod
    if test:
        # print(f"{n}C{r} = {ret}")
        pass
    return ret


def inv(n, mod):
    return power(n, mod - 2)


def power(n, p):
    if p == 0:
        return 1
    if p % 2 == 0:
        return (power(n, p // 2) ** 2) % mod
    if p % 2 == 1:
        return (n * power(n, p - 1)) % mod


if __name__ == "__main__":
    main()

Submission status: Accepted

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

def main():
    n, k=map(int, input().split())
    a=np.array(list(map(int, input().split())), dtype=np.int64)
    f=np.array(list(map(int, input().split())), dtype=np.int64)
    a=np.sort(a)
    f=np.sort(f)[::-1]
    l,r=0,10**12
    while l<=r:
        m=(l+r)//2
        tr=np.clip(a-m//f,0,None).sum()
        if tr>k:
            l=m+1
        else:
            r=m-1
    print(l)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import numpy as np

n, k = map(int, readline().split())
a = np.array(readline().split(), np.int64)
f = np.array(readline().split(), np.int64)
a.sort()
f.sort()
f = f[::-1]
a_sum = a.sum()
left = - 1
right = 10 ** 12

while left + 1 < right:
    mid = (left + right) // 2
    if a_sum - np.minimum(a, mid // f).sum() <= k:
        right = mid
    else:
        left = mid

print(right)