Overview

Among the damaged fruits, ship only those with sugar content less than \(K\) as substandard products, and find their count and total sugar content.

Analysis

In this problem, for each fruit we need to check two conditions: “is it damaged?” and “is its sugar content less than \(K\)?”, and count those that satisfy both conditions.

A naive approach would be to linearly search whether each fruit’s number is contained in \(B_1, B_2, \ldots, B_M\) every time, resulting in a worst-case time complexity of \(O(N \times M)\). Since the constraints allow \(N, M\) up to \(2 \times 10^5\), this would require up to \(4 \times 10^{10}\) comparisons, which cannot be processed within the time limit (TLE).

To solve this, by storing the “damaged fruit numbers” in a data structure such as a set beforehand, we can determine whether each fruit is damaged in \(O(1)\). This reduces the overall time complexity to \(O(N + M)\).

Algorithm

1. Read input: total number of fruits \(N\), number of damaged fruits \(M\), threshold sugar content \(K\), sugar content list \(A\) for each fruit, and damaged fruit number list \(B\).
2. Convert the damaged fruit numbers into a set damaged (for fast membership checking).
3. For each fruit \(i = 1, 2, ..., N\):
   • Check whether the fruit’s number is in damaged (i.e., whether it is damaged).
   • If it is, further check whether its sugar content \(A[i-1]\) is less than \(K\).
   • If both conditions are satisfied, update the counter and the sugar content total.
4. Output the final counter and sugar content total.

Complexity

• Time complexity: \(O(N + M)\)
• Space complexity: \(O(M)\)

Implementation Notes

• Fruit numbers are 1-indexed (starting from 1), but array indices are 0-indexed, so be careful when accessing elements (e.g., A[i - 1]).

• By converting the damaged fruit list \(B\) to a set type set(), fast element checking becomes possible.

  Source Code

# 入力の読み込み
N, M, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

# 規格外品の個数と糖度合計
count = 0
total_sugar = 0

# 傷のある果物を集合で管理して高速に検索できるようにする
damaged = set(B)

# 各果物について判定
for i in range(N):
    fruit_index = i + 1  # 果物の番号は1-indexed
    if fruit_index in damaged:  # 傷があるか？
        if A[i] < K:  # 糖度がK未満か？
            count += 1
            total_sugar += A[i]

# 結果の出力
print(count, total_sugar)

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