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
import os,io
input=io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
n,k=map(int,input().split())
a=list(map(int,input().split()))
f=list(map(int,input().split()))
a.sort()
f.sort()
f.reverse()
if sum(a)<=k:
  print(0)
  sys.exit()
pointer=0
l=0
r=0
for i in range(n):
  r=max(r,a[i]*f[i])
while l+1<r:
  try1=(r+l)//2
  required=0
  for i in range(n):
    required+=(max(0,a[i]-try1//f[i]))
  if required>k:
    l=try1
  else:
    r=try1
required=0
for i in range(n):
  required+=(max(0,a[i]-l//f[i]))
if required>k:
  print(r)
else:
  print(l)

Submission status: Accepted

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

import numpy as np

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

# X秒で完食できるか二分探索

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

def isOk(x):
  return A.sum() - np.minimum(A, x // F).sum() <= K
  
while abs(ok - ng) > 1:
  mid = abs(ok + ng) // 2
  if isOk(mid):
    ok = mid
  else:
    ng = mid
    
print(ok)

Submission status: Accepted

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

lo, hi = -1, 10 ** 18 + 1
while hi - lo > 1:
    mid = (lo + hi) // 2
    if sum(max(0, a[i] - mid // f[i]) for i in range(n)) <= k:
        hi = mid
    else:
        lo = mid

print(hi)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
# sys.setrecursionlimit(10**6)
# buff_readline = sys.stdin.buffer.readline
buff_readline = sys.stdin.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


class Mod:
    def __init__(self, m):
        self.m = m

    def add(self, a, b):
        return (a + b) % self.m

    def sub(self, a, b):
        return (a - b) % self.m

    def mul(self, a, b):
        return ((a % self.m) * (b % self.m)) % self.m

    def div(self, a, b):
        return self.mul(a, pow(b, self.m-2, self.m))

    def pow(self, a, b):
        return pow(a, b, self.m)


class Bisect:
    def __init__(self, func):
        self.__func = func

    def bisect_left(self, x, lo, hi):
        while lo < hi:
            mid = (lo+hi)//2
            if self.__func(mid) < x:
                lo = mid+1
            else:
                hi = mid
        return lo

    def bisect_right(self, x, lo, hi):
        while lo < hi:
            mid = (lo+hi)//2
            if x < self.__func(mid):
                hi = mid
            else:
                lo = mid+1
        return lo

def f(n):
    r = 1
    for i in range(1, n+1):
        r *= i
    return r

@mt
def slv(N, K, A, F):
    A.sort()
    F.sort(reverse=True)

    def f(x):
        y = 0
        for a, f in zip(A, F):
            b = a - x//f
            if b > 0:
                y += b
        if y <= K:
            return 1

        return 0

    return Bisect(f).bisect_left(1, 0, 10**18)






def main():
    N, K = read_int_n()
    A = read_int_n()
    F = read_int_n()
    print(slv(N, K, A, F))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
# sys.setrecursionlimit(10**6)
# buff_readline = sys.stdin.buffer.readline
buff_readline = sys.stdin.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


class Mod:
    def __init__(self, m):
        self.m = m

    def add(self, a, b):
        return (a + b) % self.m

    def sub(self, a, b):
        return (a - b) % self.m

    def mul(self, a, b):
        return ((a % self.m) * (b % self.m)) % self.m

    def div(self, a, b):
        return self.mul(a, pow(b, self.m-2, self.m))

    def pow(self, a, b):
        return pow(a, b, self.m)


class Bisect:
    def __init__(self, func):
        self.__func = func

    def bisect_left(self, x, lo, hi):
        while lo < hi:
            mid = (lo+hi)//2
            if self.__func(mid) < x:
                lo = mid+1
            else:
                hi = mid
        return lo

    def bisect_right(self, x, lo, hi):
        while lo < hi:
            mid = (lo+hi)//2
            if x < self.__func(mid):
                hi = mid
            else:
                lo = mid+1
        return lo

def f(n):
    r = 1
    for i in range(1, n+1):
        r *= i
    return r

@mt
def slv(N, K, A, F):
    A.sort()
    F.sort(reverse=True)

    def f(x):
        y = 0
        for a, f in zip(A, F):
            b = a - x//f
            if b > 0:
                y += b
        if y <= K:
            return 1

        return 0

    return Bisect(f).bisect_left(1, 0, 10**19)






def main():
    N, K = read_int_n()
    A = read_int_n()
    F = read_int_n()
    print(slv(N, K, A, F))


if __name__ == '__main__':
    main()

Submission status: Accepted

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

times = As * Fs

ng = -1
ok = np.amax(times)+1

while abs(ok - ng) > 1:
    mid = (ok + ng) // 2
    k = np.sum(np.maximum(np.ceil((times - mid) / Fs), 0))
    if k > K:
        ng = mid
    else:
        ok = mid

print(ok)

Submission status: Accepted

Solution code:
import sys
import numpy as np

readline = sys.stdin.buffer.readline

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

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


def binary_search(min_n, max_n):

    while max_n - min_n != 1:
        tn = (min_n + max_n) // 2
        if judge(tn):
            max_n = tn
        else:
            min_n = tn

    return max_n


def judge(tn):

    k = 0
    if np.maximum(0, A - tn // F).sum() <= K:
        return True
    else:
        return False


def solve():

    ans = binary_search(-1, 10**12)
    print(ans)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
A_array = list(map(int, input().split()))
F_array = list(map(int, input().split()))

A_array.sort()
F_array.sort()
F_array = F_array[::-1]

X = 0
Y = 10 ** 12

while(Y - X > 0):
    mid = (X + Y) // 2
    k = 0
    for a, f in zip(A_array, F_array):
        m = mid // f
        # print(a, f, k)
        k += max(0, a - m)
    if k <= K:
        Y = mid
    else:
        if Y - X == 1:
            break
        X = mid

print(Y)

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
     
def main():
    n, k = LI()
    a = sorted(LI())
    f = sorted(LI())[::-1]
    ok = 10**12
    ng = -1

    def can(x):
        times = 0
        for i in range(n):
            if f[i] * a[i] > m:
                times += ((f[i] * a[i] - m) // f[i] + 1)
                if (f[i] * a[i] - m) % f[i] == 0:
                    times -= 1
        if times <= k:
            return True
        return False

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

main()

Submission status: Accepted

Solution code:
from sys import stdin
import numpy as np
def main():
    #入力
    readline=stdin.readline
    n,k=map(int,readline().split())
    A=np.array(list(map(int,readline().split())),dtype=np.int64)
    A=np.sort(A)[::-1]
    F=np.array(list(map(int,readline().split())),dtype=np.int64)
    F=np.sort(F)

    l=-1
    r=10**12
    while l<r-1:
        x=(l+r)//2
        A_after=np.minimum(x//F,A)
        cnt=(A-A_after).sum()
        if cnt<=k: r=x
        else: l=x

    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=sorted(A)
F=sorted(F)[::-1]
import numpy as np
a=np.array(A)
f=np.array(F)

low=-1
high=10**18

while high-low>1:
  d=(high+low)//2
  #0かa-d//fの大きい値を採用するnp.maximum　
  if np.maximum(0,a-d//f).sum()<=K:
    high=d
  else:
    low=d
print(high)

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import permutations
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7


#############
# Main Code #
#############

# 3人、5回修行できる
N, K = getNM()
# 消化コスト
A = getList()
# 食べにくさ
F = getList()

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

ng = -1
ok = 10 ** 12 + 1

def judge(limit):
    cnt = 0
    for i in range(N):
        # limit // F[i] 消費コストとして許される値
        # A[i] - (limit // F[i]) 消費コストとして許される値との差
        cnt += max(0, A[i] - (limit // F[i]))
    return cnt

while ok - ng > 1:
    mid = (ok + ng) // 2
    margin = judge(mid)

    # 差がK以下であれば修正可能
    # もうちょい下のmidも試してみる
    if K >= margin:
        ok = mid
    else:
        ng = mid
print(ok)

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc144/submissions/8168248
# is_okでscoreを割るアイディア

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


def main():
    N, K = map(int, input().split())
    *A, = sorted(map(int, input().split()))
    *F, = sorted(map(int, input().split()), reverse=True)

    def is_ok(score):
        rest = K
        for a, f in zip(A, F):
            max_a = score // f
            rest -= max(0, a - max_a)
            if rest < 0: return False
        return True

    ans = binary_search(ok=10 ** 12, ng=-1, func=is_ok)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    def meguru_bisect(left, right):
        """
        is_okを定義して下さい
        :param left: 取りうる最小の値-1
        :param right: 取りうる最大の値+1
        :return: is_okを満たす最小(もしくは最大)の値
        """
        while abs(left - right) > 1:
            mid = (left + right) // 2
            if is_ok(mid):
                right = mid
            else:
                left = mid
        return right

    def is_ok(x):
        total = 0
        for i in range(n):
            total += max(0, A[i] - x // F[i])
        return total <= k

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

    left = -1
    right = 10 ** 12 + 1
    res = meguru_bisect(left, right)
    print(res)


if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
def solve(B,G,x):
  sums = 0
  for i in range(N):
    req = B[i] - x//G[i] 
    sums += max(0,req)
  if sums <= K:
    return True
  else:
    return False

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

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

L = []
MAX = 0
for i in range(N):
  temp = A[i]*F[i]
  MAX = max(MAX,temp)
ng = 1
ok = MAX+1
while abs(ng-ok) > 1:
  mid = (ok+ng)//2
  #print(mid,solve(A,F,mid))
  if solve(A,F,mid):
    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())))
F = sorted(list(map(int,input().split())),reverse=True)
if K>=sum(A):
    ans = 0
else:
    low = 0
    high = 10**12
    while high-low>1:
        mid = (high+low)//2
        B = A[:]
        cnt = 0
        for i in range(N):
            if B[i]*F[i]>mid:
                cnt += (B[i]-mid//F[i])
        if cnt<=K:
            high = mid
        else:
            low = mid
    ans = high
print(ans)

Submission status: Accepted

Solution code:
import os,io
input=io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
n,k=map(int,input().split())
a=list(map(int,input().split()))
f=list(map(int,input().split()))
a.sort()
a.reverse()
f.sort()
maxproduct=0
for i in range(n):
  maxproduct=max(f[i]*a[i],maxproduct)
l1=0
r1=maxproduct
while True:
  l2=l1
  r2=(l1+r1)//2
  if l2==r2:
    break
  counter=0
  for i in range(n):
    c=r2//f[i]
    while (c+1)*f[i]<=r2:
      c+=1
    counter+=max(0,a[i]-c)
  if counter<=k:
    r1=r2
  else:
    l1=r2
if l1==r1:
  print(r2)
else:
  counter=0
  r2=l1
  for i in range(n):
    c=r2//f[i]
    while (c+1)*f[i]<=r2:
      c+=1
    counter+=max(0,a[i]-c)
  if counter<=k:
    print(l1)
  else:
    print(r1)

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
def main():
    n,k=map(int,input().split())
    A=list(map(int,input().split()))
    F=list(map(int,input().split()))
    F.sort(reverse=True)
    A.sort()
    right=10**12
    left=-1
    while right-left>1:#区間(left,right]に解Xがある
        x=(right+left)//2
        k_sum=0
        for i in range(n):
            k_sum+=max(0,A[i]-x//F[i])
            if k_sum>k:
                left=x
                break
        else:
            right=x
    print(right)
    

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)

import numpy as np
a = np.array(a)
f = np.array(f)

low = -1
hi = 10**18

while hi-low > 1:
    ave = (hi+low)//2
    if np.maximum(0,a-ave//f).sum() <= k:
        hi = ave
    else:
        low = ave

print(hi)

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
A = [int(i) for i in input().split()]
A.sort()
F = [int(i) for i in input().split()]
F.sort(reverse=True)

left = -1
right = 10**12
def f(x): return sum(max(A[i]-x//F[i],0) for i in range(n)) <= 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 math

N,K,*AF = map(int, open(0).read().split())
A = sorted(AF[:N])
F = sorted(AF[N:],reverse=True)
left = 0
right = max(A) * max(F)
while left != right:
    mid = (left+right) // 2
    temp = 0
    for i in range(N):
        temp += max(A[i]-math.floor(mid/F[i]),0)
        if temp > K:
            left = mid + 1
            break
    else:
        right = mid
print(left)

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()))
if sum(A) <= K:
  print(0)
  exit()
A.sort()
F.sort(reverse=True)

l,r = -1,10**12+1

while r-l > 1:
  m = (l+r)//2

  k = 0
  for i in range(N):
    a,f = A[i], F[i]
    k += max(0,a-(m//f))

  if k <= K:
    r = m
  else:
    l = m

print(r)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
aa = list(map(int, input().split()))
ff = list(map(int, input().split()))

a = sorted(aa, reverse=True)
f = sorted(ff)

def C(x):
    ret = 0
    for i in range(n):
        ret += max(0, a[i] - x // f[i])
    return ret

lb = -1
ub = 10 ** 12 + 1
while (ub - lb) > 1:
    mid = (ub + lb) // 2

    if C(mid) > k:
        lb = mid
    else:
        ub = mid
print(ub)

Submission status: Accepted

Solution code:
import math
#import numpy as np
import queue
from collections import deque,defaultdict
import heapq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    n,k = map(int,ipt().split())
    a = [int(i) for i in ipt().split()]
    f = [int(i) for i in ipt().split()]
    a.sort()
    f.sort(reverse=True)
    l = 0
    r = 10**12
    while l < r:
        mid = l+(r-l)//2
        cst = 0
        for i in range(n):
            cst += max(0,a[i]-math.floor(mid/f[i]))
        if cst <= k:
            r = mid
        else:
            l = mid+1
    print(l)
    return

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import numpy as np

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

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

Asum = sum(A)

def test(X):
    return (Asum - np.minimum(A, X//F).sum() <= K)

l = -1
r = 10**12

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

ans = r
print(ans)

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
sys.setrecursionlimit(10**8)
#mod = 10**9+7
#mod = 998244353
#INF = 10**18
#eps = 10**-7

def main():
    N,K = map(int,readline().split())
    A = list(map(int,readline().split()))
    F = list(map(int,readline().split()))
    A.sort()
    F.sort(reverse=True)
    
    ng = -1
    ok = 10**12+100
    while ok - ng > 1:
        mid = (ok + ng) // 2
        if sum(max(0,a-mid//f) for a,f in zip(A,F)) <= K:
            ok = mid
        else:
            ng = mid
    print(ok)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

ng = -1
ok = 10**12+100
while ok - ng > 1:
    mid = (ok + ng) // 2
    if sum(max(0,a-mid//f) for a,f in zip(A,F)) <= K:
        ok = mid
    else:
        ng = mid
print(ok)

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)

ng = -1
ok = 10**12+100
while ok - ng > 1:
    mid = (ok + ng) // 2
    if sum(max(0,a-mid//f) for a,f in zip(A,F)) <= K:
        ok = mid
    else:
        ng = mid
print(ok)

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)
ng = -1
ok = 10**12+100
while ok - ng > 1:
    mid = (ok + ng) // 2
    c = 0
    for a,f in zip(A,F):
        c += max(0,a-mid//f)
    if c <= K:
        ok = mid
    else:
        ng = mid
print(ok)

Submission status: Accepted

Solution code:
import bisect
n,k=map(int,input().split())
a=sorted(list(map(int,input().split())))[::-1]
b=sorted(list(map(int,input().split())))
ma=a[0]*b[-1]
mi=0
if sum(a)<k+1:
  ma=0
for i in range(n):
  a[i]=a[i]*b[i]
while abs(ma-mi)>1:
  now=0
  for i in range(n):
    now+=max(0,(a[i]-(mi+ma)//2+b[i]-1)//b[i])
  if now>k:
    mi=(ma+mi)//2
  else:
    ma=(ma+mi)//2
print(ma)

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 = 10**12
l = -1

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

def nibutan(low,hi):
    while True:
        ave = (low+hi)//2
        if test(ave):
            hi = ave
        else:
            low = ave
        if hi-low == 1:
            break
    return hi

print(nibutan(l,r))

Submission status: Accepted

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

def Z(): return int(input())
def ZZ(): return [int(_) for _ in input().split()]

def main():
    N, K = ZZ()
    A = sorted(ZZ(), reverse=True)
    F = sorted(ZZ())

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

    cost = list()
    for a, f in zip(A, F): cost.append(a*f)

    ok = 10 ** 12
    ng = -1

    while ok - ng > 1:
        mid = (ok+ng)//2
        cc = 0
        for i in range(N): cc += max(0, (cost[i]-mid+F[i]-1)//F[i])
        if cc <= K: ok = mid
        else: ng = mid
    print(ok)

    return

if __name__ == '__main__':
    main()

Submission status: Accepted

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

def Z(): return int(input())
def ZZ(): return [int(_) for _ in input().split()]

def main():
    N, K = ZZ()
    A = sorted(ZZ(), reverse=True)
    F = sorted(ZZ())

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

    cost = list()
    for a, f in zip(A, F): cost.append(a*f)

    ok = 10 ** 12
    ng = -1

    for _ in range(45):
        mid = (ok+ng)//2
        cc = 0
        for i in range(N): cc += max(0, (cost[i]-mid+F[i]-1)//F[i])
        if cc <= K: ok = mid
        else: ng = mid
    print(ok)

    return

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)
lst = []
maxi = 0
for i in range(n):
    lst.append([a[i]*f[i], f[i]])
    maxi = max(maxi, a[i]*f[i])

left = -1 # 不可能
right = maxi # 可能
while left+1 < right:
    mid = (left+right)//2
    cnt = 0
    for i in range(n):
        lsti = lst[i]
        if lsti[0] > mid:
            sa = lsti[0] - mid
            cnt += (sa+lsti[1]-1) // lsti[1]
    if cnt <= k:
        right = mid
    else:
        left = mid
print(right)

Submission status: Accepted

Solution code:
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 ** 9)
INF = 10 ** 19
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()
B.sort(reverse=1)

def check(m):
    C = [0] * N
    for i in range(N):
        C[i] = m // B[i]
    res = 0
    for i in range(N):
        res += max(A[i] - C[i], 0)
    return res <= K

res = bisearch_min(-1, 10**12+1, check)
print(res)

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)

def is_ok(x):
    c = 0
    for i in range(n):
        a = A[i]
        f = F[i]
        if a >= x//f:
            c += a-x//f
    if c <= k:
        return True
    else:
        return False

if is_ok(0):
    print(0)
    exit()

l = 0
r = 10**18
while l+1 < r:
    c = (l+r)//2
    if is_ok(c):
        r = c
    else:
        l = c
print(r)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from collections import *

def judge(x):
    B = [x//Fi for Fi in F]
    cnt = 0
    
    for Ai, Bi in zip(A, B):
        cnt += max(0, Ai-Bi)
    
    return cnt<=K

def binary_search():
    l, r = 0, 10**14
    
    while l<=r:
        m = (l+r)//2
        
        if judge(m):
            r = m-1
        else:
            l = m+1
    
    return l

N, K = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
F = list(map(int, input().split()))
F.sort(reverse=True)
print(binary_search())

Submission status: Accepted

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

def test(x):
    res = 0
    for i in range(N):
        t = A[i] * F[i]
        if t > x:
            res += math.ceil((t - x) / F[i])
    
    return res <= K

ng = -1
ok = 10**18

while ng + 1 < ok:
    mid = (ng + ok) // 2
    if test(mid):
        ok = mid
    else:
        ng = mid
print(ok)

Submission status: Accepted

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

INF = 10**20
def main():
    N,K = map(int,input().split())
    A=list(map(int,input().split()))
    F=list(map(int,input().split()))

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

    def c(s): # sに対して単調減少
        sum_x = 0
        for i in range(N):
            a,f=A[i],F[i]
            tp = s//f
            if not a <= tp:
                sum_x += a-tp

        return sum_x <= K

    l=-1
    r=10**20
    while r-l>1:
        mid = (l+r)//2
        if c(mid):
            r = mid
        else:
            l = mid

    print(r)

if __name__ == "__main__":
  main()

Submission status: Accepted

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

import numpy as np

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

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

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

Submission status: Accepted

Solution code:
import bisect
import collections
import functools
import heapq
import math
import sys
from collections import deque
from collections import defaultdict
input = sys.stdin.readline
MOD = 10**9+7

N,K = map(int,(input().split()))
A = list(map(int,(input().split())))
F = list(map(int,(input().split())))
A.sort(reverse=True)
F.sort()
time = []
for i in range(N):
    time.append((A[i]*F[i],F[i]))

l = -1
r = 10**12
ans = 0
tmp = -1
while ans != tmp:
    c = 0
    tmp = ans
    for i in range(N):
        if time[i][0] > ans:
            c += (time[i][0] - ans -1)//time[i][1] +1
    if c > K:
        l = ans
    else:
        r = ans
    ans = (l+r+1)//2
print(ans)

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)
d=[[a[i]*f[i],f[i]] for i in range(n)]
r=max([di[0] for di in d])+1
l=0
x=(l+r)//2
while r-l>1:
  if r-l==2:
    cnt=0
    for di,fi in d:
      cnt+=max(0,(di-l+fi-1)//fi)
    if cnt<=k:
      x=l
    else:
      x=l+1
    break
  cnt=0
  for di,fi in d:
    cnt+=max(0,(di-x+fi-1)//fi)
  if cnt>k:
    l,r=x,r
  else:
    l,r=l,x+1
  x=(l+r)//2
if r-l==2:
  if cnt>k:
    x=l+1
  else:
    x=l

print(x)

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)

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

s = -1
l = 10**12
while(l-s > 1):
    mid = (l-s)//2 + s
    c = 0
    for i in range(N):
        if T[i] > mid:
            if (T[i] - mid) % F[i] == 0:
                c += (T[i] - mid) // F[i]
            else:
                c += (T[i] - mid) // F[i] + 1
    if c > K:
        s = mid
    else:
        l = mid
print(l)