Overview

Given the prices of \(N\) types of side dishes, this problem asks you to calculate the total price of a “bento” (boxed meal) for each of \(M\) orders, where each order specifies a combination of side dishes.

Analysis

The core of this problem is “how to efficiently retrieve and sum up the prices of the side dishes specified in each order.”

1. Data Management

The number of side dish types \(N\) is at most \(2 \times 10^5\), and there are equally many prices \(W_i\). By storing these in an array (a list in Python), we can retrieve the price \(W_i\) of side dish number \(i\) in \(O(1)\) using it as an index.

2. Complexity Estimation

For each order \(j\), the number of selected side dishes is \(K_j\). To compute the total price for all orders, we need a total of \(\sum K_j\) addition operations. Looking at the constraints, \(\sum K_j \leq 10^6\), which is small enough that a straightforward summation will comfortably fit within the time limit.

3. Fast Input/Output

In this problem, the total number of input values is very large (over \(10^6\) at maximum). Repeatedly calling Python’s standard input() function can consume significant time on I/O processing alone, potentially resulting in a Time Limit Exceeded (TLE) verdict. Therefore, techniques such as reading all input at once using sys.stdin.read().split() are effective for speeding things up.

Algorithm

1. Create the price table: Store the side dish prices \(W_1, W_2, \dots, W_N\) in a list. Since dish numbers start from 1, using a list of size \(N+1\) with 1-indexed access makes the implementation smoother.
2. Process the orders:
   • For each order \(j\), go through the specified side dish numbers \(A_{j, 1}, A_{j, 2}, \dots, A_{j, K_j}\) in order.
   • Look up each price from the price table and compute the total.
3. Output: Print the results for all orders in order.

Complexity

• Time complexity: \(O(N + \sum K_j)\)
  • Creating the price table takes \(O(N)\), and scanning through all side dishes across all orders takes \(O(\sum K_j)\). Within the given constraints, this amounts to roughly \(10^6\) operations, which runs efficiently.
• Space complexity: \(O(N + \sum K_j)\)
  • Memory is needed to store the side dish prices and all the input order data.

Implementation Tips

• Fast I/O: By reading all data at once with sys.stdin.read().split() and converting to integers, you can efficiently handle a large volume of numbers.

• List slicing and sum: In Python, you can compute sums concisely and efficiently using generator expressions like sum(W[id] for id in list_of_ids), or by utilizing clever slicing techniques.

• Batch output: Instead of calling print multiple times, accumulate results in a list and output them all at once using '\n'.join() to speed up the output processing.

  Source Code

import sys

def main():
    # 入力を一括で読み込み、空白で分割して整数のリストに変換します。
    # これにより、大量の入力を高速に処理することが可能です。
    try:
        input_str = sys.stdin.read().split()
        if not input_str:
            return
        data = list(map(int, input_str))
    except EOFError:
        return

    # N: おかずの種類数, M: 注文の件数
    N = data[0]
    M = data[1]

    # おかずの価格 W を 1-indexed で保持します。
    # data[2] から data[N+1] までがおかず 1 から N の価格に対応します。
    W = [0] * (N + 1)
    W[1:N+1] = data[2:N+2]

    # pos: 現在処理している注文の K_j (おかずの数) が格納されているインデックス
    pos = N + 2
    results = []

    # 各注文について合計金額を計算します。
    for _ in range(M):
        # K はこの注文で選ばれたおかずの数です。
        K = data[pos]
        
        # data[pos+1] から data[pos+K] までが選ばれたおかずの番号です。
        # スライスとジェネレータ式を用いて、合計金額を効率的に算出します。
        current_order_sum = sum(W[dish_id] for dish_id in data[pos + 1 : pos + 1 + K])
        
        # 計算結果を文字列としてリストに追加します。
        results.append(str(current_order_sum))
        
        # 次の注文の K_j の位置までポインタを進めます。
        pos += K + 1

    # すべての結果を改行で連結して一括出力します。
    sys.stdout.write('\n'.join(results) + '\n')

if __name__ == '__main__':
    main()

---

This editorial was generated by gemini-3-flash-thinking.