Overview

This is a simple aggregation problem where you calculate each dish’s score (base score + arrangement score) and find their total sum.

Analysis

The key points of this problem are as follows:

Understanding the Problem

• There are \(N\) types of base recipes, each with a base score \(A_i\)
• You make \(M\) dishes, and each dish’s score is determined by “the base score \(A_{B_j}\) of the base recipe” + “the arrangement score \(S_j\)”
• Find the total score of all dishes

Verification with a Concrete Example

For example, suppose there are 3 recipes with base scores \(A = [100, 200, 150]\), and you make the following 2 dishes: - Dish 1: Based on recipe 2, with arrangement score \(+50\) → Score = \(200 + 50 = 250\) - Dish 2: Based on recipe 1, with arrangement score \(-30\) → Score = \(100 + (-30) = 70\)

Total score = \(250 + 70 = 320\)

Key Points of This Problem

This problem can be solved sufficiently with a straightforward approach. Simply calculating and summing the score for each dish in order poses no issues in terms of computational complexity.

However, note the following: - Since array indices are 0-based, the base score of the \(B_j\)-th recipe must be accessed as A[B_j - 1] - The total score can become very large, but in Python there is no need to worry about integer overflow

Algorithm

1. Read \(N\) and \(M\)
2. Read the array of base scores \(A\)
3. Initialize a variable total representing the total score to \(0\)
4. In a loop of \(M\) iterations, for each dish:
   • Read the base recipe number \(B\) and arrangement score \(S\)
   • Add \(A[B-1] + S\) to total
5. Output total

Complexity

• Time complexity: \(O(N + M)\)
  • \(O(N)\) to read the array of base scores
  • \(O(M)\) to calculate the scores of \(M\) dishes
• Space complexity: \(O(N)\)
  • \(O(N)\) to store the array of base scores \(A\)

Implementation Notes

• 1-indexed to 0-indexed conversion: In the problem statement, base recipes are numbered starting from 1, but Python arrays start from index 0. Therefore, the base score corresponding to recipe number \(B\) is accessed as A[B - 1].

• Negative arrangement scores: The arrangement score \(S_j\) can take negative values, so a dish’s score may be lower than the base score.

• Overflow: Since \(A_i\) can be up to \(10^9\) and \(M\) can be up to \(10^5\), the total can reach approximately \(2 \times 10^{14}\), but Python automatically handles large integers, so this is not a problem.

  Source Code

def main():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    
    total = 0
    for _ in range(M):
        B, S = map(int, input().split())
        total += A[B - 1] + S
    
    print(total)

if __name__ == "__main__":
    main()

---

This editorial was generated by claude4.5opus.