Untitled
unknown
plain_text
5 months ago
1.8 kB
6
Indexable
#!/bin/python3 import sys import bisect import heapq def countMaximumDays(lend, payback): n = len(lend) # Pair lend and payback amounts lenders = list(zip(lend, payback)) # Sort lenders by lend amount, then by payback amount lenders.sort(key=lambda x: (x[0], x[1])) # Map lend amounts to min-heaps of payback amounts lend_to_paybacks = {} for l, p in lenders: if l not in lend_to_paybacks: lend_to_paybacks[l] = [] # Push payback amounts into a min-heap for each lend amount heapq.heappush(lend_to_paybacks[l], p) # Create a sorted list of lend amounts lend_amounts = sorted(lend_to_paybacks.keys()) day = 0 prev_payback = 0 while True: # Find the index of the smallest lend amount >= prev_payback idx = bisect.bisect_left(lend_amounts, prev_payback) if idx == len(lend_amounts): break # No lender can cover the payback lend_amount = lend_amounts[idx] # Get the lender with the minimal payback amount payback_i = heapq.heappop(lend_to_paybacks[lend_amount]) if not lend_to_paybacks[lend_amount]: # Remove lend amount if no lenders are left lend_amounts.pop(idx) del lend_to_paybacks[lend_amount] prev_payback = payback_i day += 1 return day if __name__ == '__main__': n = int(sys.stdin.readline()) lend = [] for _ in range(n): lend_item = int(sys.stdin.readline()) lend.append(lend_item) n2 = int(sys.stdin.readline()) payback = [] for _ in range(n2): payback_item = int(sys.stdin.readline()) payback.append(payback_item) result = countMaximumDays(lend, payback) print(result)
Editor is loading...
Leave a Comment