Overview

This is a problem where you calculate the purchase amount for each of the \(M\) purchase records while considering the store’s membership discount system, and then find the total.

Analysis

This is a simple problem where you only need to determine the following for each purchase record:

• Non-member (\(S_j = 0\)): Use the regular price \(A_{P_j}\) of product \(P_j\) as is.
• Member (\(S_j = 1\)): Use the price discounted by \(K\) yen from the regular price, but it cannot go below \(0\) yen.

For example, when \(K = 30\): - A product with regular price \(100\) yen → member price is \(\max(100 - 30, 0) = 70\) yen - A product with regular price \(20\) yen → member price is \(\max(20 - 30, 0) = 0\) yen (it becomes free)

No special algorithm is needed; it is sufficient to process the \(M\) records sequentially and compute the total. Even a straightforward approach comfortably fits within the constraints (\(M \leq 10^5\)).

Algorithm

1. Read \(N, M, K\) and the list of regular prices \(A\).
2. Initialize the total amount total to \(0\).
3. Process the \(M\) purchase records in order:
   • Retrieve the regular price \(A_{P_j}\) corresponding to product number \(P_j\) (since the array is 0-indexed, use \(A[P_j - 1]\)).
   • If the customer is a member (\(S_j = 1\)), update the price to \(\max(A_{P_j} - K,\ 0)\).
   • Add the purchase amount \(= \text{price} \times D_j\) to total.
4. Output total.

Concrete Example

Consider the input example with \(N=3, M=2, K=30\) and regular prices \([100, 50, 20]\).

Total: \(300 + 0 = 300\) yen

Complexity

• Time complexity: \(O(N + M)\)
  • \(O(N)\) for reading the list of regular prices, and \(O(M)\) for processing the \(M\) purchase records.
• Space complexity: \(O(N)\)
  • \(O(N)\) for storing the regular price list \(A\).

Implementation Notes

• 1-indexed to 0-indexed conversion: Product numbers start from \(1\), but Python lists start from \(0\), so you need to use A[p - 1].

• Using the max function: Use max(price - K, 0) to ensure the price does not become negative due to the membership discount. If you forget this, products with a regular price smaller than \(K\) will result in a negative price, leading to WA.

• Integer type range: The answer can be up to \(10^{15}\), but since Python does not have integer overflow, no special handling is needed (in C++ and similar languages, long long would be required).

  Source Code

N, M, K = map(int, input().split())
A = list(map(int, input().split()))
total = 0
for _ in range(M):
    s, p, d = map(int, input().split())
    price = A[p - 1]
    if s == 1:
        price = max(price - K, 0)
    total += price * d
print(total)

This editorial was generated by claude4.6opus-thinking.