Overview

For packages that were not cancelled, convert each package’s weight to the number of units (the value obtained by dividing the weight by \(K\) and rounding down), then find the total sum.

Analysis

Problem Breakdown

• There are \(N\) packages, of which \(M\) are cancelled
• For each delivered package (\(N - M\) packages), calculate the number of units \(\lfloor T_i / K \rfloor\) and find the total sum

Efficient Cancellation Checking

To determine whether a package was delivered, if we linearly search the cancellation list \(D\) each time, a single check takes \(O(M)\), resulting in \(O(N \times M)\) overall.

Example: When \(N = 200,000\) and \(M = 100,000\), up to \(2 \times 10^{10}\) comparisons may be needed in the worst case, causing TLE (Time Limit Exceeded).

Solution: Using a Set

By storing the cancelled tracking numbers in a set, we can determine whether a given number was cancelled in average \(O(1)\) time. This significantly reduces the overall computational complexity.

Algorithm

1. Read \(N\), \(M\), \(K\)
2. Store each package’s weight \(T_1, T_2, \ldots, T_N\) in an array
3. Store the cancelled tracking numbers \(D_1, D_2, \ldots, D_M\) in a set
4. For tracking numbers \(1\) through \(N\) in order, do the following:
   • If the tracking number is not in set \(D\) (i.e., not cancelled), add the number of units \(\lfloor T_i / K \rfloor\) to the total
5. Output the total

Concrete Example: - \(N=5\), \(M=2\), \(K=100\) - \(T = [250, 80, 350, 120, 500]\) - \(D = \{2, 4\}\) (tracking numbers 2 and 4 are cancelled)

Delivered packages are tracking numbers 1, 3, 5: - Number 1: \(\lfloor 250 / 100 \rfloor = 2\) - Number 3: \(\lfloor 350 / 100 \rfloor = 3\) - Number 5: \(\lfloor 500 / 100 \rfloor = 5\)

Total: \(2 + 3 + 5 = 10\)

Complexity

• Time Complexity: \(O(N + M)\)
  • Building the set takes \(O(M)\)
  • Checking and computing for each package takes \(O(N)\) (membership check in a set is average \(O(1)\))
• Space Complexity: \(O(N + M)\)
  • \(O(N)\) for the weight array
  • \(O(M)\) for the cancellation set

Implementation Notes

1. Using a Set: In Python, by using set(), element existence checks can be performed efficiently. Searching a list with the in operator takes \(O(M)\), but with a set it takes average \(O(1)\).

2. Case when \(M = 0\): When there are no cancellations, the third line does not exist in the input. To handle this exceptional input format, we process the input using try-except.

3. Note that tracking numbers are 1-indexed: Arrays are 0-indexed, but tracking numbers start from 1. Since T[i] represents the weight of the package with tracking number \(i+1\), we handle this in the loop by setting management_number = i + 1.

4. Integer Division: In Python, the // operator performs floor division. This corresponds to \(\lfloor a / b \rfloor\).

   Source Code

def main():
    line1 = input().split()
    N, M, K = int(line1[0]), int(line1[1]), int(line1[2])
    
    T = list(map(int, input().split()))
    
    if M > 0:
        D = set(map(int, input().split()))
    else:
        # M=0の場合、3行目が空行または存在しない可能性がある
        try:
            line3 = input().split()
            D = set(map(int, line3)) if line3 else set()
        except:
            D = set()
    
    total = 0
    for i in range(N):
        management_number = i + 1
        if management_number not in D:
            total += T[i] // K
    
    print(total)

if __name__ == "__main__":
    main()

---

This editorial was generated by claude4.5opus.