Overview

Given the base scores of each basic recipe, along with the base recipe number and arrangement score for each dish, the problem asks to find the total score of all dishes.

Analysis

This problem is very straightforward. For each dish, we calculate “base score of the underlying basic recipe + arrangement score” and simply sum them all up. Although the constraints have \(N\) and \(M\) up to \(10^5\) which is large, the processing for each dish only involves a lookup from the basic recipe array and an addition, so it can be handled sufficiently fast.

Algorithm

1. First, read the base scores \(A_1, A_2, \ldots, A_N\) of the basic recipes into an array
2. Then read the information for \(M\) dishes (base recipe number \(B_j\) and arrangement score \(S_j\))
3. For each dish, calculate \(A[B_j-1] + S_j\) and add it to the running total
4. Output the final total

Since array indices start from 0, we need to subtract 1 from the base recipe number \(B_j\) when accessing the array.

Complexity

• Time complexity: \(O(N + M)\)
  • \(O(N)\) for reading the basic recipes
  • \(O(M)\) for processing each dish
• Space complexity: \(O(N)\)
  • For storing the array of basic recipes

Implementation Notes

• By reading all input data at once before processing, efficient I/O is possible

• Subtracting 1 from the base recipe number allows correct access to array indices

• The total may become a large number, so care must be taken regarding integer overflow. However, in Python this is not an issue since arbitrary-precision integers are handled automatically

  Source Code

import sys

def main():
    data = sys.stdin.read().split()
    n = int(data[0])
    m = int(data[1])
    A = list(map(int, data[2:2+n]))
    total = 0
    index = 2 + n
    for _ in range(m):
        b = int(data[index])
        s = int(data[index+1])
        index += 2
        total += A[b-1] + s
    print(total)

if __name__ == "__main__":
    main()

This editorial was generated by deepseekv3.