概要

各購入記録について「会員かどうか」で 1 個あたりの単価を決め、購入個数を掛けて合計するだけのシミュレーション問題です。
商品価格の参照を高速に行い、\(M\) 件を順に処理すれば求まります。

考察

重要なポイントは次の 2 つです。

• 商品 \(i\) の定価は配列 \(A\) で与えられているので、商品番号 \(P_j\) から \(A_{P_j}\) をすぐ取り出せる。
• 会員のときだけ単価が \(\max(A_{P_j} - K, 0)\) になる（0 未満にはならない）。

したがって、各購入記録 \((S_j, P_j, D_j)\) ごとに

• 非会員（\(S_j=0\)）: 単価 \(= A_{P_j}\)
• 会員（\(S_j=1\)）: 単価 \(= \max(A_{P_j}-K,0)\)

を計算し、金額 \(= \text{単価} \times D_j\) を合計すればよいです。

素朴なアプローチとして「記録ごとに全商品を探す」ような実装をすると、1 件あたり \(O(N)\) かかり、全体で \(O(NM)\) になってしまいます。
制約は \(N \le 2\times 10^5,\ M \le 10^5\) なので、この方法は間に合いません。

一方、商品番号は 1〜\(N\) の連番なので、配列アクセスで \(O(1)\) 参照できます。
これにより全体を \(O(M)\)（入力読み取り含めれば \(O(N+M)\)）で処理できます。

アルゴリズム

1. \(N, M, K\) を読む。
2. 定価配列 \(A\) を読む（Python では 0-index なので商品番号 \(p\) の価格は A[p-1]）。
3. 合計 total = 0 を用意。
4. 各購入記録について以下を行う。
   • price = A[p-1]
   • もし s == 1（会員）なら price = max(price - K, 0)
   • total += price * d
5. total を出力。

計算量

• 時間計算量: \(O(N + M)\)
  （価格配列の読み込み \(O(N)\)、購入記録の処理 \(O(M)\)）
• 空間計算量: \(O(N)\)
  （価格配列 \(A\) を保持）

実装のポイント

• 商品番号は 1-indexed、配列は 0-indexed なので A[p-1] に注意。

• 会員割引は max(price - K, 0) で 0 未満を防ぐ。

• 合計金額は大きくなる可能性があるが、Python の int ならオーバーフローの心配は不要。

• 入力が多いため sys.stdin.readline を使うと安定して高速です。

  ソースコード

import sys

def main():
    input = sys.stdin.readline

    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)

if __name__ == "__main__":
    main()

この解説は gpt-5.3-codex によって生成されました。