Overview

For each order, you simply look at the “selected side dish numbers” and add up the corresponding prices. Looking at the constraints, the total number of side dishes across all orders satisfies \(\sum K_j \le 10^6\), so processing each specification sequentially is more than fast enough.

Analysis

What we want for each order is the sum of:

• The selected side dishes \(A_{j,1}, A_{j,2}, \dots, A_{j,K_j}\)
• Their respective prices \(W_{A_{j,1}}, W_{A_{j,2}}, \dots, W_{A_{j,K_j}}\)

In other words, the answer for the \(j\)-th order is:

\(W_{A_{j,1}} + W_{A_{j,2}} + \cdots + W_{A_{j,K_j}}\)

Key Insight

Since the side dish prices \(W_i\) are all given at the beginning, if we store the “side dish number \(\to\) price” mapping in an array, we can immediately retrieve the price each time we read a side dish number in an order.

For example:

• Prices: \(W_1=300, W_2=500, W_3=200\)
• Order: \([1, 3]\)

Then the total is \(300 + 200 = 500\).

Naive Inefficient Approach

If for each order we “check all \(N\) types of side dishes every time to see if that side dish is included in the order,” each order takes at least \(O(N)\), and the overall complexity becomes \(O(NM)\).

The constraints are:

• \(N \le 2 \times 10^5\)
• \(M \le 10^5\)

So \(O(NM)\) is too large and won’t run in time.

How to Solve It

We only need to look at the side dishes that are actually included in the order. For each order, we read the \(K_j\) listed side dish numbers in sequence and add up their prices.

The total number of side dish numbers processed across all orders is \(\sum K_j \le 10^6\), so the overall time complexity is \(O(\sum K_j)\), which is sufficiently fast.

Algorithm

1. Store the side dish prices in an array W.
2. For each order:
   • Read the count \(K\)
   • Initialize a total s = 0
   • For the following \(K\) side dish numbers a, compute s += W[a]
   • Store s as the answer
3. Output all answers separated by newlines.

With this approach, we simply add the price once for each side dish number.

Complexity

• Time complexity: \(O\left(N + \sum_{j=1}^{M} K_j\right)\)
• Space complexity: \(O(N + M)\)

Implementation Notes

• Since the input size is large, we use sys.stdin.buffer.read().split() to read everything at once for speed.

• Side dish numbers start from \(1\), so in the code we use W = [0] + ... to make it 1-indexed. This allows us to directly retrieve the price for side dish number i using W[i].

• Instead of calling print for each line, it is faster to accumulate results in a string array and output them all at once with "\n".join(ans).

  Source Code

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    it = iter(data)

    N = next(it)
    M = next(it)

    W = [0] + [next(it) for _ in range(N)]

    ans = []
    for _ in range(M):
        K = next(it)
        s = 0
        for _ in range(K):
            s += W[next(it)]
        ans.append(str(s))

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

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.4-high.