Overview

Among the multiple viewing permits that Aoki holds, we collect all books that can be read using at least one of them, and find the sum of the difficulty levels of those books.

Analysis

First, each viewing permit that Aoki holds has a “permission level,” and it allows reading books with difficulty at or below that level.
Therefore, the books Aoki can read are those that are “viewable by at least one permit.”
In other words, this means all books with difficulty at or below “the highest permission level among the permits Aoki holds.”

For example, if the permission levels of Aoki’s permits are \([3, 7, 5]\), he can read any book with difficulty \(7\) or below (the maximum).
In this way, even when there are multiple permits, we only need to know their maximum value.

If we naively “check all permits for each book to determine whether it can be read,” the worst case requires \(N \times K\) computations, which will TLE given the large constraints (\(N, K \leq 2 \times 10^5\)).

Instead, we can compute efficiently by finding only the “maximum permission level” and using it to handle all readable books at once.
Furthermore, if the book difficulties are sorted, we can use binary search to quickly determine “up to which position the books are readable.”

Algorithm

1. Look at all the permission levels corresponding to the viewing permits Aoki holds, and find their maximum value \(max\_level\).
2. Sort the list of book difficulties \(P\) in ascending order.
3. Use binary search to find the number of books in the sorted \(P\) with difficulty at most \(max\_level\) (in Python, use bisect.bisect_right).
4. Compute and output the sum of the difficulties of those books.

Example

Sample input:

N=5, M=3, K=2
P = [1, 4, 6, 2, 8]
L = [3, 7, 5]
T = [1, 3] (Aoki holds the 1st and 3rd permits)

• The permission levels of Aoki’s permits are: \(L[0]=3\), \(L[2]=5\) → the maximum is \(5\)
• Sort the book difficulties: \(P = [1, 2, 4, 6, 8]\)
• Books with difficulty \(5\) or below are the first 3: \(1, 2, 4\)
• Sum: \(1 + 2 + 4 = 7\)

Complexity

• Time complexity: \(O(N \log N + K)\)
  • \(O(N \log N)\) for sorting
  • \(O(K)\) for finding the maximum of the viewing permits
  • Binary search and partial sum computation are less than \(O(N)\)
• Space complexity: \(O(N + M + K)\) (for storing all inputs in lists)

Implementation Notes

• The permit indices are 1-based, so be careful to subtract \(-1\) when accessing arrays.

• The sum of book difficulties can become very large. In languages like Python this is not a concern, but in C++ and similar languages, be careful about overflow.

• By using techniques for fast input reading (e.g., sys.stdin.read), you can handle large inputs efficiently.

  Source Code

import sys
import bisect

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    idx = 0
    N = int(data[idx]); idx += 1
    M = int(data[idx]); idx += 1
    K = int(data[idx]); idx += 1
    
    P = list(map(int, data[idx:idx+N])); idx += N
    L = list(map(int, data[idx:idx+M])); idx += M
    T = list(map(int, data[idx:idx+K])); idx += K
    
    # 閲覧許可証の許可レベルを取得し、最大値を求める
    max_level = 0
    for t in T:
        max_level = max(max_level, L[t - 1])
    
    # 本の難易度をソート
    P.sort()
    
    # 難易度がmax_level以下である本の数を二分探索で求める
    pos = bisect.bisect_right(P, max_level)
    
    # 総和を計算
    total = sum(P[:pos])
    print(total)

if __name__ == "__main__":
    main()

This editorial was generated by qwen3-coder-480b.