Overview

For each order, sum up the prices corresponding to the selected side dish numbers and output the result. This is a straightforward aggregation problem.

Analysis

While this problem appears very simple at first glance, careful attention to the data size is necessary.

• There are at most \(N = 2 \times 10^5\) types of side dishes
• There are at most \(M = 10^5\) orders
• The total number of side dishes across all orders \(\sum K_j\) is at most \(10^6\)

Simply summing up the prices of side dishes for each order is sufficient, but the key observation is the constraint that the total number of side dishes across all orders is at most \(10^6\). This ensures that even if we iterate through \(K_j\) side dishes per order, the total number of operations across all orders stays within \(10^6\).

For example, consider the following input:

• There are 3 types of side dishes with prices \(W = [100, 200, 300]\)
• Order 1: side dishes 1, 3 → total \(100 + 300 = 400\)
• Order 2: side dish 2 → total \(200\)

For each order, we simply look up the price array \(W\) using the specified side dish numbers as indices and sum them up.

Algorithm

1. Store the prices of \(N\) types of side dishes in an array \(W\) (0-indexed).
2. For each of the \(M\) orders, do the following:
   • Read the \(K_j\) side dish numbers \(A_{j,1}, A_{j,2}, \dots, A_{j,K_j}\) included in the order.
   • For each side dish number \(A_{j,k}\), sum up \(W[A_{j,k} - 1]\) (converting from 1-indexed to 0-indexed).
   • Save the total price for output.
3. Output the total prices for all orders together.

Complexity

• Time complexity: \(O\!\left(N + \displaystyle\sum_{j=1}^{M} K_j\right)\)
  • \(O(N)\) for reading the price array, and a total of \(O\!\left(\sum K_j\right)\) (at most \(10^6\)) for processing all orders.
• Space complexity: \(O(N + M)\)
  • \(O(N)\) for the price array \(W\), and \(O(M)\) for the output array.

Implementation Notes

• Speeding up input: In Python, the standard input() is slow, so we replace it with sys.stdin.readline for faster input. This is an essential technique for problems with large amounts of input.

• Speeding up output: Calling print() for each order would be slow with \(M\) output calls, so we accumulate the results in an array and output them all at once using sys.stdout.write() at the end.

• Index conversion: Side dish numbers are given as 1-indexed, but Python lists are 0-indexed, so we need to subtract 1 when accessing, like W[line[i] - 1].

• Parsing input lines: Each order line starts with \(K_j\) (the number of side dishes), followed by \(K_j\) side dish numbers. We read the entire line as a list at once, treating line[0] as \(K_j\) and line[1] through line[K_j] as the side dish numbers.

  Source Code

import sys
input = sys.stdin.readline

def main():
    N, M = map(int, input().split())
    W = list(map(int, input().split()))
    out = []
    for _ in range(M):
        line = list(map(int, input().split()))
        K = line[0]
        total = 0
        for i in range(1, K + 1):
            total += W[line[i] - 1]
        out.append(str(total))
    sys.stdout.write('\n'.join(out) + '\n')

main()

This editorial was generated by claude4.6opus-thinking.