Overview

This problem asks you to compute the total price for each order by summing up the prices corresponding to the specified side dish numbers, then output the results. By directly referencing the price array, all orders can be processed efficiently.

Analysis

The key point is that “each order is given as a list of side dish numbers.” Therefore, what needs to be done for each order is simple: for each listed number \(a\), add the price \(W_a\).

For example, if the prices are \(W_1=300, W_2=500, W_3=200\), and the order is \((2, 1, 3)\), the total is \(300+200=500\).

A naive implementation that “searches for the price of each side dish every time” (e.g., linear search through a list) would make each lookup slow, potentially causing the overall solution to exceed the time limit. In this problem, side dish numbers range from \(1\) to \(N\), so by directly accessing an array, you can retrieve the price in \(O(1)\).

Additionally, since the constraint guarantees \(\sum_{j=1}^{M} K_j \le 10^6\), an implementation that processes each selected side dish exactly once is sufficiently fast.

Algorithm

1. Read \(N, M\).
2. Read the price array \(W\). In implementation, using W = [0] + ... to make it 1-indexed is convenient, allowing direct access via W[a] for dish number \(a\).
3. For each order:
   • Read the first value on the line as \(K_j\).
   • For each of the following \(K_j\) side dish numbers \(A_{j,k}\), compute s += W[A_{j,k}].
   • Append the total s to the output array.
4. Finally, output everything joined by newlines.

Complexity

• Time complexity: \(O\!\left(N + \sum_{j=1}^{M} K_j\right)\) (Reading input and adding each selected side dish once)
• Space complexity: \(O(N + M)\) (Storing the price array and the output strings. The temporary array for a single input line is at most \(O(N)\))

Implementation Tips

• Use sys.stdin.readline for fast input.

• Make the price array 1-indexed to prevent off-by-one index bugs.

• Rather than calling print each time, accumulate results in an array and output with "\n".join(out) for faster I/O.

  Source Code

import sys

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

    N, M = map(int, input().split())
    W = [0] + list(map(int, input().split()))  # 1-indexed

    out = []
    for _ in range(M):
        data = list(map(int, input().split()))
        k = data[0]
        s = 0
        for a in data[1:1 + k]:
            s += W[a]
        out.append(str(s))

    sys.stdout.write("\n".join(out))

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.3-codex.