Overview

Given \(N\) types of products and \(M\) purchase records, the problem asks you to calculate the total sales amount, taking into account the member discount (\(K\) yen off per item, with a minimum price of \(0\) yen).

Analysis

The key points in this problem are “correctly calculating the per-item price depending on whether the customer is a member or not” and “efficiently processing a large amount of data”.

1. Price Calculation

When a member purchases product \(i\) (listed price \(A_i\)), the price becomes \(A_i - K\) yen. However, since the problem states “the discount does not exceed the listed price, and the price does not go below \(0\) yen,” if \(A_i - K\) becomes negative, it must be treated as \(0\) yen. Expressed as a formula, this is \(\max(A_i - K, 0)\).

2. Efficient Processing

Looking at the constraints, the number of product types \(N\) is up to \(2 \times 10^5\) and the number of records \(M\) is up to \(10^5\), which are very large. The answer can be obtained by repeating the following steps for each purchase record: 1. Determine the listed price \(A_{P_j}\) from the product number \(P_j\) (retrievable in \(O(1)\) using an array). 2. Check the membership flag \(S_j\) and determine the unit price. 3. Add “unit price \(\times\) quantity \(D_j\)” to the total amount.

Since each step runs in constant time, the overall time complexity is \(O(N + M)\), which is well within the time limit.

Algorithm

1. Store the listed prices \(A_1, A_2, \ldots, A_N\) in an array (a list in Python). It is convenient to map product numbers \(1 \sim N\) to array indices \(0 \sim N-1\).
2. Initialize a variable total_sales to \(0\) to hold the total amount.
3. Read each of the \(M\) purchase records one by one.
   • If the customer is a member (\(S_j = 1\)): unit price \(v = \max(A_{P_j} - K, 0)\)
   • If the customer is not a member (\(S_j = 0\)): unit price \(v = A_{P_j}\)
   • Add \(v \times D_j\) to total_sales.
4. Output the final total_sales.

Complexity

• Time complexity: \(O(N + M)\)
  • Reading the listed prices takes \(O(N)\), and processing the purchase records takes \(O(M)\). Each record is processed in constant time.
• Space complexity: \(O(N)\)
  • An array of length \(N\) is needed to store the listed prices of the products.

Implementation Notes

• Fast I/O: Since \(N\) and \(M\) can be large, in Python it is faster to read all input at once using sys.stdin.read().split() rather than calling input() repeatedly.

• Handling large numbers: The answer can be as large as \(10^{15}\), but Python natively supports arbitrary-precision integers (integers of any size), so you can compute directly without worrying about overflow.

• Index adjustment: Product numbers in the problem start from \(1\), but arrays in programming languages typically start from \(0\). You need to subtract \(1\) from the index when accessing, such as A[p - 1].

  Source Code

import sys

def solve():
    # 入力をすべて一括で読み込み、スペースや改行で分割してリストにします。
    # 大量の入力を効率的に処理するために sys.stdin.read().split() を使用します。
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # イテレータを使用して各値を順番に取得します。
    it = iter(input_data)
    
    # N: 商品の種類数, M: 購入記録の件数, K: 会員の割引額
    N = int(next(it))
    M = int(next(it))
    K = int(next(it))
    
    # A: 各商品の定価リスト (商品番号 i は A[i-1] に対応)
    A = [int(next(it)) for _ in range(N)]
    
    total_sales = 0
    
    # M 件の購入記録を順番に処理します。
    for _ in range(M):
        s = int(next(it)) # 会員かどうか (1: 会員, 0: 非会員)
        p = int(next(it)) # 購入した商品の番号 (1-indexed)
        d = int(next(it)) # 購入した個数
        
        # 定価を取得
        price = A[p - 1]
        
        if s == 1:
            # 会員の場合、1個あたりの価格は max(定価 - K, 0)
            member_price = price - K
            if member_price < 0:
                member_price = 0
            total_sales += member_price * d
        else:
            # 非会員の場合、1個あたりの価格は定価どおり
            total_sales += price * d
            
    # すべての購入記録の合計金額を出力します。
    # Pythonは標準で多倍長整数をサポートしているため、10^15のような大きな値も扱えます。
    print(total_sales)

if __name__ == '__main__':
    solve()

---

This editorial was generated by gemini-3-flash-thinking.