概要

青木君が持つ閲覧許可証で「少なくとも1枚で読める本」の集合は、結局「許可レベルの最大値以下の本すべて」になるので、その最大値を求めて該当する本の難易度を合計します。

考察

各閲覧許可証 \(j\) は「難易度が \(L_j\) 以下の本をすべて読める」という性質を持っています。ここで重要な観察は次の通りです。

• 青木君が持つ許可証の許可レベルの最大値を \(X=\max(L_{T_1},\ldots,L_{T_K})\) とすると、
  • 難易度 \(p \le X\) の本は、その最大レベルの許可証（あるいは同等以上のもの）で読める
  • 難易度 \(p > X\) の本は、どの許可証でも読めない
    よって「少なくとも1枚で読める本」＝「難易度が \(X\) 以下の本すべて」となります。

素朴に考えると、 - 各許可証ごとに「\(L_{T_k}\) 以下の本」を列挙・加算する（\(K\) 回走査） - さらに重複（複数の許可証で読める同じ本）を除く必要がある

などをやりたくなりますが、これは最悪で \(O(NK)\) となり、制約 \(N,M \le 2\times 10^5\) では間に合いません。また重複管理も複雑になります。

そこで「最大の許可レベルだけ見ればよい」という性質を使い、問題を一気に単純化します。

（例） - 本の難易度 \(P=[2,5,7]\) - 持っている許可証の許可レベルが \([3,6]\) なら最大は \(6\) - 読める本は難易度 \(\le 6\) の本なので \(2+5=7\)

アルゴリズム

1. 青木君が持っている許可証番号 \(T_1,\ldots,T_K\) を見て、対応する許可レベル \(L_{T_k}\) の最大値 \(X\) を求める。
2. 全ての本の難易度 \(P_i\) について、\(P_i \le X\) を満たすものだけ合計する。
3. 合計値を出力する。

計算量

• 時間計算量: \(O(N+K)\)（入力読み込みを含めると全体で \(O(N+M+K)\)）
• 空間計算量: \(O(N+M+K)\)（配列を保持するため）

実装のポイント

• 許可証番号 \(T_k\) は \(1\) 始まりなので、Python の配列参照では L[t-1] のように \(0\) 始まりへ変換します。

• 合計は最大で \(N \times 10^9\) 程度になり得ますが、Python の int は任意精度なのでそのまま足して問題ありません。

• 入力が大きいので sys.stdin.buffer.read() で高速に読み取っています。

  ソースコード

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    it = iter(data)
    N = next(it)
    M = next(it)
    K = next(it)

    P = [next(it) for _ in range(N)]
    L = [next(it) for _ in range(M)]
    T = [next(it) for _ in range(K)]

    max_level = 0
    for t in T:
        lv = L[t - 1]
        if lv > max_level:
            max_level = lv

    ans = 0
    for p in P:
        if p <= max_level:
            ans += p

    print(ans)

if __name__ == "__main__":
    main()

この解説は gpt-5.2-high によって生成されました。