Overview

Given \(N\) packages where \(M\) of them are cancelled, compute the total weight of the remaining packages converted into a certain unit.

Analysis

In this problem, for each package with weight \(T_i\), we compute the number of units \(\lfloor T_i / K \rfloor\) (the value of \(T_i\) divided by \(K\), rounded down), and output the total number of units for all packages that were not cancelled.

A naive approach would be to store the list of cancelled packages in an array and, for each package, perform a linear search to check “is this package cancelled?”. However, this method requires up to \(M\) comparisons per package, resulting in an overall time complexity of \(O(N \times M)\), which would not finish in time (TLE) in the worst case (\(N, M = 2 \times 10^5\)).

Instead, by storing the tracking numbers of cancelled packages in a set, we can quickly determine “was a given package cancelled?”. Adding elements to and searching in a set can be done in \(O(1)\) on average, significantly reducing the overall time complexity.

Additionally, in Python, it is common to use sys.stdin.read for fast standard input, which is also adopted in this solution.

Algorithm

1. Read all input at once, split it, and store it in variables.
2. Store the weight \(T_i\) of each package in a list.
3. Store the tracking numbers \(D_j\) of cancelled packages in a set.
4. For each package, if its tracking number (1-indexed) is not in the cancellation set, add \(\lfloor T_i / K \rfloor\) to the total.
5. Output the final total.

Complexity

• Time complexity: \(O(N + M)\)
  (Each package is processed in \(O(1)\), with \(N\) packages and \(M\) cancellations)
• Space complexity: \(O(N + M)\)
  (Storing the list of packages and the set of cancelled tracking numbers)

Implementation Notes

• By storing the cancelled tracking numbers in a set instead of a list, we achieve fast membership checking.

• Since tracking numbers are 1-indexed, when using 0-indexed list indices, we need to compare with i + 1.

• sys.stdin.read is used for faster input processing.

• Note that the solution correctly handles the case \(M = 0\), since not in always returns True for an empty set.

  Source Code

import sys
input = sys.stdin.read

def main():
    data = input().split()
    N = int(data[0])
    M = int(data[1])
    K = int(data[2])
    
    T = list(map(int, data[3:3+N]))
    
    D = set(map(int, data[3+N:3+N+M]))
    
    total_units = 0
    for i in range(N):
        if (i + 1) not in D:
            total_units += T[i] // K
    
    print(total_units)

if __name__ == "__main__":
    main()

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