概要

各料理の得点 \(A_{B_j}+S_j\) を \(M\) 回分足し合わせ、合計得点を求める問題です。

考察

料理 \(j\) の得点は「ベースとなる基本レシピの基本点」\(A_{B_j}\) と「アレンジ点」\(S_j\) の和で決まります。よって、求めたい合計は

[ \sum{j=1}^{M} (A{B_j} + S_j) ]

です。

重要な点は、各料理について必要なのは 配列 \(A\) から 1 回参照して \(S_j\) を足すだけ ということです。
たとえば \(A=[10,20,30]\)、\((B,S)=(2,5),(1,-3)\) なら、得点は \(20+5=25\) と \(10-3=7\)、合計は \(32\) になります。

素朴にやっても十分速いですが、\(N,M \le 10^5\) なので、Pythonでは input() を \(M\) 回呼ぶような実装だと入出力がボトルネックになり遅くなることがあります。そこで、まとめて読み込む高速入力（sys.stdin.buffer.read()）を使うと安全です。

アルゴリズム

1. \(N, M\) を読む。
2. 長さ \(N\) の配列 \(A\)（基本点）を読む。
3. 合計 total=0 を用意する。
4. 各料理 \(j=1..M\) について、\((B_j, S_j)\) を読み、
   • \(B_j\) は 1-indexed なので 0-indexed に直して b = B_j - 1
   • total += A[b] + S_j を行う。
5. total を出力する。

計算量

• 時間計算量: \(O(N+M)\)（\(A\) を読むのに \(N\)、各料理の処理に \(M\)）
• 空間計算量: \(O(N)\)（配列 \(A\) を保持）

実装のポイント

• \(B_j\) は入力では \(1\) から始まるため、Pythonの配列アクセス用に B_j-1 に変換します。

• 合計は最大で \(M \times (10^9 + 10^9) \approx 2 \times 10^{14}\) 程度になり得ますが、Pythonの整数はオーバーフローしないのでそのまま扱えます。

• 入力が大きいので、sys.stdin.buffer.read().split() でまとめて読み、イテレータで順に取り出すと高速です。

  ソースコード

import sys

def main():
    data = sys.stdin.buffer.read().split()
    it = iter(data)
    N = int(next(it))
    M = int(next(it))
    A = [int(next(it)) for _ in range(N)]
    total = 0
    for _ in range(M):
        b = int(next(it)) - 1
        s = int(next(it))
        total += A[b] + s
    sys.stdout.write(str(total))

if __name__ == "__main__":
    main()

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