結果

問題 No.2422 regisys?
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 19:25:09
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,961 bytes
コンパイル時間 472 ms
コンパイル使用メモリ 81,976 KB
実行使用メモリ 190,800 KB
最終ジャッジ日時 2025-06-12 19:25:38
合計ジャッジ時間 27,263 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 46 WA * 15
権限があれば一括ダウンロードができます

ソースコード

diff # 

def main():
    import sys
    input = sys.stdin.read().split()
    idx = 0
    N, M = int(input[idx]), int(input[idx+1])
    idx +=2
    A = list(map(int, input[idx:idx+N]))
    idx +=N
    B = list(map(int, input[idx:idx+N]))
    idx +=N
    buyers = []
    for _ in range(M):
        T = int(input[idx])
        C = int(input[idx+1])
        buyers.append((T, C))
        idx +=2

    def compute_max_sold(order):
        first_type, second_type = order
        taken = [False] * N

        # Process first_type
        first_buyers = sorted([c for t, c in buyers if t == first_type], reverse=True)
        sorted_first_items = sorted(range(N), key=lambda i: (A[i] if first_type == 0 else B[i]))
        ptr = len(sorted_first_items) - 1
        for c in first_buyers:
            while ptr >= 0:
                item_idx = sorted_first_items[ptr]
                price = A[item_idx] if first_type == 0 else B[item_idx]
                if price > c or taken[item_idx]:
                    ptr -= 1
                else:
                    break
            if ptr >= 0:
                taken[item_idx] = True
                ptr -= 1

        # Process second_type
        second_buyers = sorted([c for t, c in buyers if t == second_type], reverse=True)
        sorted_second_items = sorted(range(N), key=lambda i: (A[i] if second_type == 0 else B[i]))
        ptr = len(sorted_second_items) - 1
        for c in second_buyers:
            while ptr >= 0:
                item_idx = sorted_second_items[ptr]
                price = A[item_idx] if second_type == 0 else B[item_idx]
                if price > c or taken[item_idx]:
                    ptr -= 1
                else:
                    break
            if ptr >= 0:
                taken[item_idx] = True
                ptr -= 1

        return sum(taken)

    max_sold = max(compute_max_sold((0, 1)), compute_max_sold((1, 0)))
    print(N - max_sold)

if __name__ == "__main__":
    main()
0