Overview

Among the \(N\) packages scheduled for delivery, we need to find the value of each non-canceled package’s weight divided by \(K\) (rounded down to the nearest integer), and compute the total sum.

Analysis

The steps required to solve this problem are the following three points:

1. Accurately determine which package management numbers have been canceled.
2. Identify the non-canceled packages and calculate the “number of units” for each.
3. Compute the total sum of the calculated unit numbers.

The key thing to pay attention to here is the constraints. The number of packages \(N\) can be up to \(2 \times 10^5\), which is relatively large, so efficient processing is required.

For example, when checking whether a given management number \(i\) has been canceled, if we search through the entire cancellation list \(D\) from beginning to end each time, a single check takes up to \(O(M)\) time. Repeating this \(N\) times results in an overall complexity of \(O(N \times M)\), which requires up to about \(4 \times 10^{10}\) operations and will not finish within the time limit (TLE).

To solve this problem, we need a technique that allows us to determine whether management number \(i\) has been canceled in \(O(1)\). Specifically, we use a boolean array or a hash set (such as Python’s set).

Algorithm

We proceed with the following steps:

1. Read input: Read \(N, M, K\), the list of weights \(T\), and the list of canceled numbers \(D\).
2. Organize cancellation information: Prepare an array is_canceled of length \(N+1\), initializing all values to False. For each number \(d\) in list \(D\), update is_canceled[d] = True.
3. Calculate unit numbers and sum them up:
   • Check each \(i\) from \(1\) to \(N\) in order.
   • If is_canceled[i] is False, then that package has been delivered.
   • Using the weight \(T_i\) of the delivered package, calculate the number of units \(\lfloor T_i / K \rfloor\) and add it to the running total.
   • In Python, integer division (floor division) can be easily performed using the // operator.
4. Output the result: Output the final total.

Complexity

• Time complexity: \(O(N + M)\)
  • Reading input takes \(O(N + M)\), creating the cancellation information array takes \(O(M)\), and computing the sum of unit numbers takes \(O(N)\). Since \(N, M \le 2 \times 10^5\), this runs sufficiently fast.
• Space complexity: \(O(N)\)
  • \(O(N)\) memory is used for the list storing package weights and the array for cancellation checks.

Implementation Notes

• Fast I/O: Since \(N\) and \(M\) can be large, in Python we use sys.stdin.read().split() to read all input at once and handle it as a list, which reduces execution time.

• Index management: Package management numbers start from \(1\), but arrays in programming languages typically start from \(0\). Care must be taken not to confuse the correspondence between management number \(i\) and array index (whether it’s i or i-1).

• Handling large numbers: The total sum of unit numbers can become a very large value, but since Python natively supports arbitrary-precision integers, we can compute without worrying about overflow.

  Source Code

import sys

def solve():
    # 全ての入力を一度に読み込み、空白（スペース、改行）で分割してリスト化します。
    # N, M, K が最大で 2*10^5 程度の規模であれば、この方法が効率的です。
    input_data = sys.stdin.read().split()
    
    # 入力が空の場合の例外処理
    if not input_data:
        return
    
    # 1行目の N (荷物の総数), M (キャンセル数), K (1ユニットの重さ) を取得
    N = int(input_data[0])
    M = int(input_data[1])
    K = int(input_data[2])
    
    # 荷物の重さ T_i は input_data のインデックス 3 から N 個分
    # キャンセルされた管理番号 D_j はインデックス 3 + N から M 個分
    
    # キャンセルされた管理番号を効率よく判定するため、boolean 配列を作成
    # 管理番号は 1 から N なので、サイズ N + 1 の配列を用意します。
    is_canceled = [False] * (N + 1)
    for i in range(3 + N, 3 + N + M):
        d = int(input_data[i])
        is_canceled[d] = True
    
    total_units = 0
    # 各荷物について、キャンセルされていなければユニット換算して加算
    for i in range(N):
        management_id = i + 1
        if not is_canceled[management_id]:
            # 重さ T_i は input_data[3 + i] に格納されている
            weight = int(input_data[3 + i])
            # 小数点以下切り捨て（整数除算）
            total_units += weight // K
            
    # 最終的な総和を出力
    print(total_units)

if __name__ == '__main__':
    solve()

This editorial was generated by gemini-3-flash-preview.