結果
問題 | No.2422 regisys? |
ユーザー |
![]() |
提出日時 | 2023-08-20 20:24:23 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 705 ms / 2,000 ms |
コード長 | 1,447 bytes |
コンパイル時間 | 214 ms |
コンパイル使用メモリ | 82,644 KB |
実行使用メモリ | 150,240 KB |
最終ジャッジ日時 | 2024-12-14 02:45:56 |
合計ジャッジ時間 | 19,470 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 61 |
ソースコード
# マッチング、最大流ではMLEした# Ford_FulkersonができるのはN100前後だけ# 公式解説はまったく違うやり方# 一般の人について、所持金の低い順に走査# それぞれの購買者について、買うことのできる商品の中で最も「MMA 部員が購入できる値段」が高いものを購入# MMA 部員について、所持金の低い順に走査# それぞれの購買者について、買うことのできる商品があったら購入# それをheapで実装from heapq import *N, M = map(int, input().split())A = list(map(int, input().split()))B = list(map(int, input().split()))A_idx_sorted = sorted(enumerate(A), key=lambda x:-x[1])people0 = []people1 = []for i in range(M):t, c = map(int, input().split())if t == 0:people0.append(c)elif t == 1:people1.append(c)people0.sort()people1.sort()H0 = []heapify(H0)for c in people0:while A_idx_sorted and A_idx_sorted[-1][1] <= c:# aを小さい順にみて、使えるaに対応するbをheappushidx, a = A_idx_sorted.pop()heappush(H0, -B[idx])if H0:# cで購入する1つだけをheappopするheappop(H0)H1 = [-b for b in H0]heapify(H1)for idx, a in A_idx_sorted:heappush(H1, B[idx])for c in people1:if H1 and H1[0] <= c:heappop(H1)# 購入されずにheapに残った個数が答えprint(len(H1))