Buggy python submission (verdict: Time Limit Exceeded):


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

max_f = A[0] * F[-1]

def binary_search(min_f, max_f):
	if min_f == max_f:
		return min_f

	mid_f = min_f + (max_f - min_f)//2
	tmp = 0
	for i in range(N):
		tmp += max(0,A[i] - mid_f // F[i])
	
	if tmp <= K:
		return binary_search(min_f, mid_f)
	else:
		return binary_search(mid_f+1, max_f)

print(binary_search(0, max_f))

Fixed submission:


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

max_f = A[0] * F[-1]

def binary_search(min_f, max_f):
	if min_f == max_f:
		return min_f

	mid_f = min_f + (max_f - min_f)//2
	tmp = 0
	for i in range(N):
		tmp += max(0,A[i] - mid_f // F[i])
	
	if tmp <= K:
		return binary_search(min_f, mid_f)
	else:
		return binary_search(mid_f+1, max_f)

print(binary_search(0, max_f))

Buggy python submission (verdict: Time Limit Exceeded):
import heapq

N, K = map(int, input().split())
A = list(map(int, input().split()))
F = list(map(int, input().split()))
A = [A[i] * (-1) for i in range(N)]
heapq.heapify(A)
heapq.heapify(F)
AF = []
for _ in range(N):
	t_a = heapq.heappop(A)
	t_f = heapq.heappop(F)
	AF.append([t_a*t_f, t_f])

heapq.heapify(AF)
for _ in range(K):
	t,f = heapq.heappop(AF)
	heapq.heappush(AF,[min(0,t+f), f])

ans, f = heapq.heappop(AF)
print(ans*(-1))

Fixed submission:


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

max_f = A[0] * F[-1]

def binary_search(min_f, max_f):
	if min_f == max_f:
		return min_f

	mid_f = min_f + (max_f - min_f)//2
	tmp = 0
	for i in range(N):
		tmp += max(0,A[i] - mid_f // F[i])
	
	if tmp <= K:
		return binary_search(min_f, mid_f)
	else:
		return binary_search(mid_f+1, max_f)

print(binary_search(0, max_f))

Buggy python submission (verdict: Time Limit Exceeded):
import heapq

N, K = map(int, input().split())
A = list(map(int, input().split()))
F = list(map(int, input().split()))
A = [A[i] * (-1) for i in range(N)]
heapq.heapify(A)
heapq.heapify(F)
AF = []
for _ in range(N):
	t_a = heapq.heappop(A)
	t_f = heapq.heappop(F)
	AF.append([t_a*t_f, t_f])

heapq.heapify(AF)
for _ in range(K):
	t,f = heapq.heappop(AF)
	heapq.heappush(AF,[min(0,t+f), f])

ans, f = heapq.heappop(AF)
print(ans*(-1))

Fixed submission:


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

max_f = A[0] * F[-1]

def binary_search(min_f, max_f):
	if min_f == max_f:
		return min_f

	mid_f = min_f + (max_f - min_f)//2
	tmp = 0
	for i in range(N):
		tmp += max(0,A[i] - mid_f // F[i])
	
	if tmp <= K:
		return binary_search(min_f, mid_f)
	else:
		return binary_search(mid_f+1, max_f)

print(binary_search(0, max_f))

Buggy python submission (verdict: Time Limit Exceeded):
import heapq

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

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

AF = [[A[i]*F[i]*(-1), F[i]] for i in range(N)]
heapq.heapify(AF)
for _ in range(K):
	t,f = heapq.heappop(AF)
	heapq.heappush(AF,[min(0,t+f), f])

ans, f = heapq.heappop(AF)
print(ans*(-1))

Fixed submission:


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

max_f = A[0] * F[-1]

def binary_search(min_f, max_f):
	if min_f == max_f:
		return min_f

	mid_f = min_f + (max_f - min_f)//2
	tmp = 0
	for i in range(N):
		tmp += max(0,A[i] - mid_f // F[i])
	
	if tmp <= K:
		return binary_search(min_f, mid_f)
	else:
		return binary_search(mid_f+1, max_f)

print(binary_search(0, max_f))