Overview

For each purchase record, compute the “actual price per item,” multiply it by the number of items purchased, and sum everything up.
The problem can be solved by straightforwardly calculating based on each product’s listed price \(A_i\) and the condition that members get a \(K\) yen discount (but the price does not go below \(0\) yen).

Analysis

What we need in this problem is to correctly compute the purchase amount for each purchase record.

For a purchase record \((S_j, P_j, D_j)\):

• The product number is \(P_j\)
• The listed price is \(A_{P_j}\)
• If non-member (\(S_j = 0\)), the price per item is \(A_{P_j}\) yen
• If member (\(S_j = 1\)), the price per item is \(\max(A_{P_j} - K, 0)\) yen

Therefore, the purchase amount for that record is:

• For non-members: \(A_{P_j} \times D_j\)
• For members: \(\max(A_{P_j} - K, 0) \times D_j\)

Summing this over all records gives the answer.

Key Observation

The number of items purchased \(D_j\) can be up to \(10^5\), but there is no need to simulate one item at a time.
Since we know the price per item, it is sufficient to compute it all at once as:

\[ \text{price} \times D_j \]

Why a Too-Naive Approach Is Problematic

For example, an implementation like “if \(D_j\) items are bought, loop one by one and accumulate the total” could result in an extremely large total sum of purchase quantities, making it unnecessarily slow.
In this problem, we only need to look at each record once, so it is important to compute on a per-record basis.

Concrete Example

For example, suppose:

• \(A_3 = 100\)
• \(K = 30\)
• The record is \((S, P, D) = (1, 3, 4)\)

Since this is a member, the price per item is:

\[ \max(100 - 30, 0) = 70 \]

So the purchase amount is:

\[ 70 \times 4 = 280 \]

Also, if \(A_3 = 20\), then:

\[ \max(20 - 30, 0) = 0 \]

and the purchase amount is \(0 \times 4 = 0\) yen.
Make sure not to forget the condition that “the price does not go below \(0\) yen.”

Algorithm

1. Read the listed price array \(A\) for the products.
2. Initialize the total amount total to \(0\).
3. For each purchase record, do the following:
   • Read \(S, P, D\)
   • If \(S = 0\), the price per item is \(A_P\)
   • If \(S = 1\), the price per item is \(\max(A_P - K, 0)\)
   • Add price * D to total
4. Finally, output total.

With this approach, we only need to process each record exactly once.

Complexity

• Time complexity: \(O(N + M)\)
• Space complexity: \(O(N)\)

Implementation Notes

• Since product numbers range from \(1\) to \(N\), it is convenient to make A an array of length N + 1 and use 1-indexed access.
• The member price must always be computed as

$\( \max(A[P] - K, 0) \)$

to ensure it does not become negative. - The total amount can become large, so be careful with integer type handling. In Python, large integers are handled automatically, so there is no concern. - In the submission code, sys.stdin.buffer.read() is used to read all input at once for faster processing.

Source Code

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    it = iter(data)

    N = next(it)
    M = next(it)
    K = next(it)

    A = [0] * (N + 1)
    for i in range(1, N + 1):
        A[i] = next(it)

    total = 0
    for _ in range(M):
        S = next(it)
        P = next(it)
        D = next(it)
        price = A[P] if S == 0 else max(A[P] - K, 0)
        total += price * D

    print(total)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.4-high.