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:
from math import ceil
N, K = map(int, input().split())
A = sorted(list(map(int, input().split())))
F = sorted(list(map(int, input().split())), reverse=True)

K = min(K, sum(A))
X = [[a, f] for a, f in zip(A, F)]

ok, ng = 10 ** 12 + 1, -1
while abs(ok - ng) > 1:
    m = (ok + ng) // 2
    k_cost = 0
    for a, f in X:
        if a * f <= m:
            continue
        else:
            k_cost += max(0, ceil(-(m / f - a)))

    if k_cost <= K:
        ok = m
    else:
        ng = m

print(ok)

Submission status: Accepted

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

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

M = 0
for i in range(N):
  M += A[i] * F[i]

def nasu(n):
  ans = 0
  for i in range(N):
    ans += max(0, A[i] - (n // F[i]))
  if ans <= K:
    return True
  else:
    return False

def hersCode():
  ok = M
  ng = -1
  while abs(ok - ng) > 1:
    mid = abs(ok + ng) // 2
    if nasu(mid):
      ok = mid
    else:
      ng = mid
  return ok

print(hersCode())

Submission status: Accepted

Solution code:
#設定
import sys
input = sys.stdin.buffer.readline

INF = float("inf")

def getlist():
	return list(map(int, input().split()))

#二分探索基本形 L:リスト x:値 n:リスト長
def Binary_Search(A, F, N, K):
	#初期化
	left = 0
	right = 10 ** 12
	ans = INF
	
	#二分探索
	while left <= right:
		mid = (left + right) // 2
		cnt = 0
		for i in range(N):
			if A[i] * F[i] > mid:
				cnt += (A[i] - int(mid // F[i]))
		if cnt <= K:
			right = mid - 1
			ans = min(ans, mid)
		else:
			left = mid + 1

	return ans

#処理内容
def main():
	N, K = getlist()
	A = getlist()
	F = getlist()
	A = sorted(A)
	F = sorted(F)[::-1]
	ans = Binary_Search(A, F, N, K)
	print(ans)

if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
import sys
from collections import Counter
input = sys.stdin.readline
sys.setrecursionlimit(100000)
def getN():
    return int(input())
def getList():
    return list(map(int, input().split()))

def check(mid, k, pairs):
    tmp = 0
    for pair in pairs:
        a,b = pair
        kari_a = mid // b
        tmp += max(a - kari_a, 0)

    if tmp <= k:
        return True
    else:
        return False


def solve():
    n, k = getList()
    cap = getList()
    foods = getList()
    cap.sort()
    foods.sort(reverse=True)
    h = []
    pairs = [(a, b) for a, b in zip(cap, foods)]
    ansmn = 0
    ansmx = 10**13
    # print(foods)
    # print(cap)
    # print([2046//p for p in foods])
    while(ansmx - ansmn > 1):
        mid = (ansmn + ansmx) // 2
        res = check(mid, k, pairs)
        if res:
            ansmx = mid
        else:
            ansmn = mid


    if check(ansmn, k, pairs):
        print(ansmn)
    else:
        print(ansmx)

def main():
    solve()


if __name__ == "__main__":
    main()


"""
10 10
95 38 9 26 36 10 69 25 44 83
6 42 33 74 75 31 73 20 70 93
"""

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)

H = 0
for i in range(n):
    H = max(H, a[i] * f[i])

if H == 0:
    print(0)
    exit()

H += 1
L = 0
while L < H:
    M = (L + H) // 2
    temp = k
    for i in range(n):
        if a[i] * f[i] > M:
            temp -= a[i] - (M // f[i])
            if temp < 0:
                break
    #print(L, H, M, temp)
    if temp < 0:
        L = M + 1
    else:
        H = M

print(L)

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 = 0
    r = 10 ** 12
    while l <= r:
        m = (l + r) // 2
        req = np.clip(aaa - m // fff, 0, None).sum()
        # print(aaa, m // fff, m, req)
        if req > k:
            l = m + 1
        else:
            r = m - 1
    return l


n, k = list(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:
N, K = map(int, input().split())
A = sorted([int(a) for a in input().split()])
F = sorted([int(a) for a in input().split()])[::-1]
l = -1
r = 10**18
while r-l > 1:
    m = (l+r)//2
    if sum([max(0, A[i] - m//F[i]) for i in range(N)]) <= K:
        r = m
    else:
        l = m
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()

ori = [0] * n
for i in range(n):
    ori[i] = a[i]*f[i]

ok = max(ori)
ng = -1
mid = (ok+ng) // 2
while ok - ng > 1:
    cnt = 0
    flg = 0
    for i in range(n):
        if ori[i] > mid:
            cnt += (a[i] - mid // f[i])
        if cnt > k:
            flg = 1
            break
    if flg:
        ng = mid
    else:
        ok = mid
    mid = (ok + ng) // 2

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)
m = 0
for i in range(n):
    m += a[i] * f[i]
l, r = -1, m
while l + 1 != r:
    m = (l + r) // 2
    tmp = 0
    for i in range(n):
        tmp += max(a[i] - m // f[i], 0)
    if k < tmp:
        l = m
    else:
        r = m
print(r)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def bisection(l,r,f,left=True,discrete=True):
    eps=1 if discrete else 10**-12
    if((not left)^f(r)): return r if left else r+1
    elif(left^f(l)): return l-1 if left else l
    while(r-l>eps):
        h=(l+r)//2 if discrete else (l+r)/2
        if((not left)^f(h)): l=h
        else: r=h
    return (l+r)/2 if not discrete else l if left else r

def resolve():
    n,k=map(int,input().split())
    A=sorted(map(int,input().split()))
    F=sorted(map(int,input().split()),reverse=1)
    def check(x):
        res=0
        for a,f in zip(A,F):
            if(a*f)<=x: continue
            res+=a-int(x/f)
        return res<=k
    print(bisection(0,10**12,check,left=False))
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()
f.sort(reverse = True)

left = -1
right = 10**18+1


while right - left > 1:
    mid = left + (right - left) // 2


    train = k
    for i in range(n):
        req = mid // f[i]
        if req < a[i]:
            train -= a[i] - req


    if train >= 0:
        right = mid
    else:
        left = mid



print(right)

Submission status: Accepted

Solution code:
import math

n, k = (int(i) for i in input().split())
alist = list(int(i) for i in input().split())
flist = list(int(i) for i in input().split())

alist=sorted(alist)
flist=sorted(flist, reverse=True)
low = 0
high = 10**12
t = (low + high) // 2

#print(alist)
#print(flist)

while (low<high):
    kaisu=0
    for i in range(n):
        wari=math.floor(t/flist[i])
        shugyo=max(alist[i]-wari,0)
        kaisu+=shugyo
    
    #print(t, kaisu, k, low, high)
    if kaisu<k:
        high=t
    elif kaisu>k:
        low=t+1
    elif kaisu==k:
        high=t #?
    if low<high:
        t=(low+high)//2
    
print(low)

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]

def test(x):
    # 全員がx秒以下に収めるための必要コストがK以下である
    return np.maximum(0,A-x//F).sum() <= K

left = -1 # 不可能目標
right = 10**13 # 可能目標
while left+1 < right:
    mid = (left+right)//2
    if test(mid):
        right = mid
    else:
        left = mid

answer = right
print(answer)

Submission status: Accepted

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

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

mx = max(a)*max(f)
mn = -1
while mx-mn>1:
    mid = (mx+mn)//2
    shugyo = 0
    for i in range(n):
        a_ = mid//f[i]
        shugyo += max(a[i]-a_,0)
    if shugyo<=k:
        mx = mid
    else:
        mn = mid

print(mx)

Submission status: Accepted

Solution code:
from math import ceil

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

def check(m):
    used = 0
    for i in range(n):
        b = ceil(a[i]-m/f[i])
        if b < 0:
            b = 0
        if a[i]-b < 0:
            return False
        used += b
        if used > k:
            return False
    return True

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

Submission status: Accepted

Solution code:

import sys
def input():
	return sys.stdin.readline().strip()

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

right = F[-1]*A[0]
left = 0

while left < right:
	mid = (left + right) // 2

	total = 0
	for i in range(N):
		if F[i]*A[i] > mid:
			add = F[i]*A[i] - mid
			if add % F[i] == 0:
				total += add//F[i]
			else:
				total += add//F[i] + 1
	#print(mid, left, right)
	if total <= K:
		judge = 1
	else:
		judge = 0

	if judge == 1: #左の区間に限定する条件
		right = mid
	else: #右の区間に限定される場合
		left = mid + 1
		mid += 1


print(mid)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(200000)
input = sys.stdin.readline
def ii(): return int(input())
def mi(): return map(int, input().rstrip().split())
def lmi(): return list(map(int, input().rstrip().split()))
def fi(): return float(input())
def mfi(): return map(float, input().rstrip().split())
def lmfi(): return list(map(float, input().rstrip().split()))
def li(): return list(input().rstrip())
def debug(*args, sep=" ", end="\n"): print("debug:", *args, file=sys.stderr, sep=sep, end=end) if not __debug__ else None
def exit(*arg): print(*arg); sys.exit()
# template

import heapq
class Heapq:
    def __init__(self, arr, desc=False):
        if desc:
            arr = [-a for a in arr]
        self.sign = -1 if desc else 1
        self.hq = arr
        heapq.heapify(self.hq)

    def pop(self):
        return heapq.heappop(self.hq) * self.sign

    def push(self, a):
        heapq.heappush(self.hq, a * self.sign)

    def top(self):
        return self.hq[0] * self.sign

def main():
    N, K = mi()
    A = lmi()
    F = lmi()
    A.sort()
    F.sort()
    F.reverse()
    ng = -1
    ok = 10**12
    while ok - ng > 1:
        mid = (ok + ng) // 2
        t = 0
        for i in range(N):
            t += max(A[i] - mid // F[i], 0)
        if t <= 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=[int(i) for i in input().split()]
F=[int(i) for i in input().split()]
A.sort()
F.sort()

def chk(x):
  ct=0
  for i in range(n):
    a,f=A[i],F[-i-1]
    ct+=max(0,a-x//f)
    if ct>k:
      return False
  if ct<=k:
    return True
  else:
    return False
l=0
r=0
for i in range(n):
  r=max(r,A[i]*F[-i-1])

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

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

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!


def binarysearch(ok,ng,isOK): #二分探索
    while(abs(ok-ng) > 1):
        mid = (ok + ng)//2
        if isOK(mid): ok = mid
        else: ng = mid
    return ok


import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline 

from heapq import *

#n = int(input())
n,k = [int(i) for i in readline().split()]
a = [int(i) for i in readline().split()]
f = [int(i) for i in readline().split()]

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


def isOK(c):
    res = 0
    for ai,fi in zip(a,f):
        p = max(0,(ai*fi-c+fi-1)//fi)
        res += p
#    print(res,c)
    return res <= k
   

print(binarysearch(10**12,-1,isOK))

"""
res = 0
for i in range(n):
    while a[i]*f[i] > 12:
        a[i] -= 1
        res += 1
        
print(res)        
"""

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
a=[int(i) for i in input().split()]
f=[int(i) for i in input().split()]
lo=0 
from math import ceil 
a.sort()
f.sort(reverse=1)
def check(mi):
    cost=0 
    for i in range(n): 
        curr=a[i]*f[i]
        if curr<mi:
            pass 
        else: 
            cost+=ceil((curr-mi)/(f[i]))
            if cost>k:
                return 0 
    return cost<=k 
hi=10**13
while lo<=hi: 
    mi=(lo+hi)>>1 
    if check(mi):
        ans=mi 
        hi=mi-1 
    else:
        lo=mi+1 
print(ans)

Submission status: Accepted

Solution code:
import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

n, k = na()
a = na()
f = na()
a.sort()
f.sort()

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


low = -1; high = 2000000000000
while high - low > 1:
    h = high+low>>1
    if ok(h, a, f, k):
        high = h
    else:
        low = h
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()))
a = sorted(a)
f = sorted(f, reverse = True)

def solve(mid):
    tmp = [0]*n
    for i in range(n):
        tmp[i] = mid // f[i]
    res = 0
    for i in range(n):
        if tmp[i] < a[i]:
            res += a[i] - tmp[i]
    #print(tmp, a)
    if res <= k:
        return True
    else:
        return False
     
ok = 10**12 + 1
ng = 0

if solve(0):
    print(0)
    exit()
    
while abs(ok - ng) > 1:
    mid = (ok + ng) // 2
    if solve(mid):
        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
while ok-ng > 1:
    mid = (ok+ng)//2
    cnt = 0

    for i,e in enumerate(a):    
        cnt += max(0,e-mid//f[i])
    if cnt <= 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(reverse=True)
f.sort()
mx=10**12
mn=-1
def test(buf):
    count=0
    for i in range(n):
        count+=max(0,a[i]-buf//f[i])
        if count>k:
            return False
    return True

while mx-mn>1:
    buf=(mx+mn)//2
    if test(buf):
        mx=buf
    else:
        mn=buf
print(mx)

Submission status: Accepted

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

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

def possible(x):
    k = K
    for i in range(N):
        if A[i]*F[i]>x:
            k -= ceil(A[i]-x/F[i])
        if k < 0:
            break
    return k >= 0


l = 0
r = 10**12
for i in range(45):
    m = (l+r)/2
    if possible(m):
        r = m
    else:
        l = m

print(round(m))

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n,k = LI()
    a = LI()
    f = LI()
    a.sort()
    f.sort(reverse = True)
    M = 0
    for i in range(n):
        M = max(M,a[i]*f[i])
    l = -1
    r = M
    while r-l > 1:
        m = (l+r)>>1
        s = 0
        for i in range(n):
            p = m//f[i]
            s += max(0,a[i]-p)
            if s > k:
                l = m
                break
        else:
            r = m
    print(r)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from heapq import heapify, heappop, heappush
from collections import defaultdict
import sys
#input = sys.stdin.readline
def inpl(): return list(map(int, input().split()))

N, K = inpl()
A = sorted(inpl())
F = sorted(inpl(), reverse=True)

OK = 10**13
NG = -1

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

while abs(OK - NG) > 1:
    m = (OK + NG)//2
    if check(m):
        OK = m
    else:
        NG = m
    
print(OK)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
A = sorted(list(map(int, input().split())), reverse = True)
F = sorted(list(map(int, input().split())))
def C(m):
    res = 0
    for i, f in enumerate(F):
        a = m//f
        if A[i]<=a:
            continue
        res+=A[i]-a
    if res>K:
        return False
    return True


ng = -1
ok = 10**13
while ok-ng>1:
    mid = (ok+ng)//2
    if C(mid):
        ok = mid
    else:
        ng = mid
print(ok)

Submission status: Accepted

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


def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    F = list(map(int, input().split()))
    A.sort()
    F.sort()
    lo = 0
    hi = A[-1] * F[-1]
    while lo < hi:
        mid = (lo + hi) // 2
        if check(N, A, F, K, mid):
            hi = mid
        else:
            lo = mid + 1
    print(lo)


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)
# print(A)
l = -1
r = 10**12 + 2
mid = (l+r)//2
while r-l>1:
    m = 0
    for i in range(n):
        aa = mid // F[i]
        m += max(0, A[i]-aa)
    if m > k:
        l = mid
    else:
        r = mid
    mid = (l+r)//2

print(l+1)

Submission status: Accepted

Solution code:

from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())

N,K = inpl()
AA = inpl()
FF = inpl()

AA.sort()
FF.sort(reverse=True)


def solve(x):
    k = 0
    for i in range(N):
        A,F = AA[i],FF[i]
        k += max(0,A - (x//F))
    return k <= K

OK = 10**18
NG = -1

while OK - NG > 1:
    mid = (NG+OK)//2
    if solve(mid):
        OK = mid
    else:
        NG = mid

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()))
F=list(map(int,input().split()))

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


MIN=0
MAX=max(A)*max(F)

while MIN!=MAX:
    mid=(MIN+MAX)//2
    score=0

    for i in range(N):
        if A[i]*F[i]>mid:
            score+=A[i]-mid//F[i]

    if score<=K:
        MAX=mid
    else:
        MIN=mid+1

print(MIN)

Submission status: Accepted

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

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


from math import ceil


def is_ok(mid):
    remain = k
    for ff, aa in zip(f, a):
        if ff * aa > mid:
            x = ceil(aa - (mid / ff))
            if x <= aa and x <= remain:
                remain -= x
            else:
                return False
    return True


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


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

Submission status: Accepted

Solution code:
def main():
    n,k=map(int,input().split())
    A=list(map(int,input().split()))
    F=list(map(int,input().split()))
    A.sort()
    F.sort(reverse=True)
    
    def count(m):
        ret=0
        for a,f in zip(A,F):
            ret+=max(0,a-(m//f))
        return ret
    ng=-1
    ok=10**12+1
    while ok-ng>1:
        mid=(ok+ng)//2
        cnt=count(mid)
        if cnt<=k:
            ok=mid
        else:
            ng=mid
    print(ok)

if __name__=='__main__':
    main()

Submission status: Runtime Error

Solution code:
N,T=map(int,input().split())
L=[]
for i in range(N):
  a,b=map(int,input().split())
  L.append((a,b))
L.sort()

DP=[[0 for i in range(T)] for j in range(N+1)]

for i in range(N):
  for j in range(T):
    if j-L[i][0]>=0 and i>0:
      DP[i][j]=max(DP[i-1][j-L[i-1][0]]+L[i-1][1],DP[i-1][j])
ans=0
for i in range(N):
  if i!=N:
    ans=max(ans,DP[i][T-1]+L[i][1])
  else:
    ans=max(ans,DP[i][T-1])

print(ans)

Submission status: Runtime Error

Solution code:
from math import ceil
def chk(A, C, x, K):
    cnt = 0
    for i in range(N):
        cnt += max(ceil(A[i]-x/C[i]), 0)
        if cnt > K:
            return False
    return True
def main():
    N, K = map(int,input().split())
    A = list(map(int,input().split()))
    C = list(map(int,input().split()))
    A.sort(reverse=True)
    C.sort()
    ng, ok = -1, 10**12
    while ok - ng > 1:
        m = (ok+ng)//2
        if chk(A, C, m, K):
            ok = m
        else:
            ng = m
    print(ok)
if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import sys
import numpy as np

if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC
    cc = CC('my_module')

    @cc.export('is_ok', '(i4[:],i4[:],i4,i4)')
    def is_ok(A, F, x, k):
        tmp = 0
        for a, f in zip(A, F):
            y = a * f
            if y > x:
                tmp += a - x // f
        return tmp <= k

    cc.compile()
    exit(0)

from my_module import is_ok
n, k = map(int, input().split())
A = np.array(list(map(int, input().split())))
F = np.array(list(map(int, input().split())))

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

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

print(ok)

Submission status: Runtime Error

Solution code:
import numpy as np
N, K= map(int, input().split())
A=[int(i) for i in input().split()]
F=[int(i) for i in input().split()]

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

lower_bound=0
upper_bound=np.max(A*F)
K_tmp=0

while upper_bound>=lower_bound:
    mid=(lower_bound+upper_bound)//2
    K_tmp=np.sum(np.maximum(A-mid//F, 0))
    if K_tmp<=K:
        upper_bound=mid-1
    else:
        lower_bound=mid+1

print(lower_bound)

Submission status: Runtime Error

Solution code:
import copy
from heapq import heappop, heapify, heappush
import math
N, K = map(int, input().split())
A = [int(i) for i in input().split()]
F = [int(i) for i in input().split()]
ans = 0
A.sort(reverse=True)
F.sort()
s = []
for i in range(N):
    s.append([A[i]*F[i], A[i], F[i]])
s.sort(reverse=True, key=lambda x: x[0])

def f(l, T):
    cur = 0
    num = 0
    S = copy.deepcopy(l)
    while cur <= K:
        if len(S) == 0:
            break
        a, b, c = S[num]
        if a <= T:
            break
        cur += math.ceil((a - T)/c)
        num += 1
    if cur <= K:
        return True
    else:
        return False

ok, ng = s[0][0], -1
while abs(ok-ng) > 1:
    mid = (ok+ng)//2
    if f(s, mid) == True:
        ok = mid
    else:
        ng = mid
print(ok)

Submission status: Runtime Error

Solution code:
from numba import njit

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

@njit
def cond(x):
    k = 0
    for a, f in zip(A, F): k += max(a - (x // f), 0)
    return True if k <= K else False 

MIN = -1
MAX = 10**12 + 1
left, right = MIN, MAX # search range
while right - left > 1:
    mid = (left + right) // 2
    if cond(mid): right = mid
    else: left = mid
print(right)

Submission status: Runtime Error

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)

Asum = sum(A)

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

l = -1
r = 10**13

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

ans = r
print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np
from numba import njit

@njit
def solve(A, F, K):
    lo = 0
    hi = 10 ** 12
    while lo < hi:
        mid = (lo + hi) // 2
        total_train = 0
        for i in range(A.shape[0]):
            need = A[i] - mid // F[i]
            total_train += need if need > 0 else 0
        if total_train <= K:
            hi = mid
        else:
            lo = mid + 1
    return lo

stdin = np.fromstring(open(0).read(), dtype=np.int64, sep=' ')
N, K = stdin[:2]
A = stdin[2: 2 + N]
F = stdin[2 + N:]
print(solve(np.sort(A)[::-1], np.sort(F), K))

Submission status: Runtime Error

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

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

while K >= 0:
  ans = 0
  idx = []
  for n in range(N):
    S = A[n] * F[n]
    if S >= ans:
      ans = S
      idx = n
  K -= 1
  A[idx] -= 1
  if ans == 0:
    break
    
print(ans)

Submission status: Runtime Error

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split())).sprt()
f=list(map(int,input().split())).sort(reverse=True)
temp=10**12
z=list(a[i]*f[i] for i in range(n))

#temp=
for i in range(k):
  q=z.index(max(z))
  z[q]-=a[q]

print(max(z))

Submission status: Runtime Error

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

for i in range(k):
  x=s.index(max(s))
  s[x]-=f[x]

Submission status: Runtime Error

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()
ng=-1
ok=10**12
while ok-ng>1:
    mid=(ok+ng)//2
    temp=0
    flag=0
    for i in range(n):
        a=mid//F[i]
        if a>A[i]:
            continue
        else:
            temp+=A[i]-a
    if temp>k:
        flag=1
    if flag:
        ng
    else:
        right=center
temp=0
for i in range(n):
    a=center//F[i]
    if a>A[i]:
        continue
    else:
        temp+=A[i]-a
if temp<=k:
    ans=left
else:
    ans=right
print(ans)

Submission status: Runtime Error

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

n,k=map(int,input().split())
A=np.array(read().split(),np.int64)
F=np.array(read().split(),np.int64)
A.sort()
F.sort()
F=F[::-1]
    
def ok(x): #チームの成績をxとするような修行の仕方が存在するか
    B=A-x//F
    return sum(B[B>0])<=k
    
l=-1
r=10**18
while r-l>1:
    mid=(r+l)//2
    if ok(mid):
        r=mid
    else:
        l=mid
print(r)

Submission status: Runtime Error

Solution code:
import math

mod = 10 ** 9 + 7

def cmb(n, i, k): #n人のうちi人に1つずつ配り、全体の個数はk個
    #print(n, i, k)
    if i == k:
        return math.factorial(n) // math.factorial(i) // math.factorial(n - i) #配り方
    tmp = math.factorial(n) // math.factorial(i) // math.factorial(n - i) #配り方
    tmp %= mod
    remain = k - i
    for j in range(1, remain + 1): #j人にくばる
        if i >= j:
            #print('a', n, i, k, ' ', i, j, remain)
            tmp *= cmb(i, j, remain)
            tmp %= mod
    return tmp % mod

n,k = map(int,input().split())
if n <= k:
    dp = [[[0, 0] for _ in range(k + 1)] for _ in range(n + 1)] #dp[i][j][0]人iまでで、j個のキャンディを配った時の幸福度, dp[i][j][1]: 何通り？
    dp[0][0][0] = 0
    for i in range(n):
        dp[i][0][1] = 1
    for i in range(k + 1):
        dp[1][i][0] = i
        dp[1][i][1] = 1
    for i in range(2, n + 1): #i人目まで決定する
        for j in range(k + 1): #j個配るときを決定する
            tmp1 = 0
            cnt = 1
            for l in range(j): #今回何個配るか？
                if j - l >= 0:
                    #print(i, j, l, dp[i - 1][j - l][0])
                    tmp2 = dp[i - 1][j - l][0] * l
                    if tmp2 > tmp1:
                        tmp1 = tmp2
                        cnt = dp[i - 1][j - l][1]
                        cnt %= mod
                    elif tmp2 == tmp1:
                        cnt += dp[i - 1][j - l][1]
                        cnt %= mod
            #print(tmp1, cnt)
            dp[i][j][0] = tmp1
            dp[i][j][1] = cnt % mod
    #print(dp)
    print(dp[n][k][1])
else:
    ans = 0
    for i in range(1, k+1): #i人で配る
        #print(n, i, k, cmb(n, i, k))
        ans += cmb(n, i, k)
        ans %= mod
        #print('')
    print(ans)