Overview

For the packages that were not cancelled, compute the sum of \(\lfloor T_i / K \rfloor\) (the integer part of dividing the weight \(T_i\) by \(K\)) and output it.

Analysis

The number of units for each package \(i\) is \(\lfloor T_i / K \rfloor\), and packages whose numbers are in the cancelled set \(\{D_1,\dots,D_M\}\) (i.e., packages that will not be delivered) are excluded from the total.

The key point here is how to efficiently determine whether “package \(i\) was cancelled.”

• Naively, for each package \(i\), searching through \(D_1,\dots,D_M\) sequentially (linear search) would require up to \(N \times M\) comparisons in the worst case. Since \(N,M \le 2\times 10^5\), this amounts to approximately \(4\times 10^{10}\) comparisons, resulting in TLE.
• Instead, we store the cancelled numbers in a set, and for each package number \(i\), we check whether it belongs to the set in average \(O(1)\) time.

Concrete example: - When \(K=10\), \(T=[5, 23, 40]\), and the cancellations are \(D=[2]\): - Package 1: \(5//10=0\) (added) - Package 2: cancelled (excluded) - Package 3: \(40//10=4\) (added) The total is \(0+4=4\).

Algorithm

1. Read \(N,M,K\) and the array \(T\) from input.
2. Read the cancelled package numbers \(D\) (when \(M>0\)) and create the set canceled = set(D).
3. For \(i=1..N\), do the following:
   • If \(i \notin canceled\), add total += T[i] // K.
4. Output total.

Complexity

• Time complexity: \(O(N+M)\) (building the set is \(O(M)\), and checking and summing for each package is \(O(N)\))
• Space complexity: \(O(M)\) (for the cancelled number set)

Implementation Notes

• Package numbers are \(1\)-indexed in the problem statement, so using something like enumerate(T, start=1) to align the numbering helps prevent mistakes.

• When \(M=0\), the third line of input does not exist. Reading all input at once with sys.stdin.buffer.read().split() and extracting only the required number of elements is a safe approach.

• The total can be as large as \(N \times (10^9 // 1) \approx 2\times 10^{14}\), but since Python’s int does not overflow, it can be handled directly.

  Source Code

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    if not data:
        return
    N, M, K = data[0], data[1], data[2]
    T = data[3:3 + N]
    D = data[3 + N:3 + N + M]
    canceled = set(D)

    total = 0
    for i, t in enumerate(T, start=1):
        if i not in canceled:
            total += t // K

    print(total)

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.