概要

各観光地の「評価値（お土産満足度の中央値）」を先に求め、評価値が高い観光地から最大 \(K\) 個まで（ただし正のものだけ）選ぶことで、合計評価値の最大値を求めます。

考察

重要な気づき

• どの観光地を選ぶかによって、各観光地の評価値自体は変わりません（観光地同士の干渉がない）。
• よって問題は次のように言い換えられます：
  「\(N\) 個の数（各観光地の評価値）があり、その中から \(0\) 個以上 \(K\) 個以下を選んで合計を最大化せよ」

このとき最適戦略は明らかで、 - 評価値が大きいものから順に選ぶ - ただし、\(0\) 個選んでもよいので、負の評価値を選ぶメリットはない（合計が減るだけ）

つまり「評価値を降順に並べて、上から最大 \(K\) 個のうち正のものだけ足す」が最適です。

素朴なアプローチがダメな理由

観光地の選び方を全探索すると \(2^N\) 通りあります。
\(N \le 100\) なので \(2^{100}\) は到底間に合いません。

この問題は「各観光地の評価値を計算して、あとは大きい順に取る」だけで解けます。

具体例

例えば評価値が \([5, 3, -1, 2]\)、\(K=2\) なら、 - 降順にして \([5, 3, 2, -1]\) - 上から最大2個の正の値を足して \(5+3=8\)
（\(K\) 個必ず選ぶ必要はないので、負の値を含めない）

アルゴリズム

1. 各観光地 \(i\) について：
   1. お土産満足度 \(V_{i,1}, \dots, V_{i,C_i}\) を昇順ソートする。
   2. 中央値は \(C_i\) が奇数なので、\(0\)-indexed で位置 \(C_i//2\) の値になる（\(\frac{C_i+1}{2}\) 番目に相当）。
   3. その中央値を「評価値」として配列 medians に入れる。
2. medians を降順にソートする。
3. 上から最大 \(K\) 個を見ていき、正の間だけ足し合わせる（\(0\) 以下が来たら以降も \(0\) 以下なので打ち切り）。
4. 合計を出力する（どれも選ばない場合は自然に \(0\) になる）。

計算量

• 時間計算量:
  各観光地でソートに \(O(C_i \log C_i)\)、さらに評価値配列のソートが \(O(N \log N)\) なので
  全体で \(O\!\left(\sum_{i=1}^{N} C_i \log C_i + N \log N\right)\)
  （制約上 \(C_i \le 99\) なので十分高速です）
• 空間計算量: \(O(\max C_i + N)\)（各観光地の配列と中央値配列）

実装のポイント

• 中央値は「昇順ソート後の vals[C//2]」で取れます（\(C\) は奇数なので一意）。

• 「\(0\) 個選んでもよい」ため、評価値が \(0\) 以下なら選ばないのが最適です。降順ソート後は、\(0\) 以下が現れた時点で打ち切れます。

• 入力がやや長いので、sys.stdin.read() でまとめて読み取る実装にすると簡潔で速いです。

  ソースコード

import sys

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

    medians = []
    for _ in range(N):
        C = next(it)
        vals = [next(it) for _ in range(C)]
        vals.sort()
        medians.append(vals[C // 2])

    medians.sort(reverse=True)
    ans = 0
    for i in range(min(K, N)):
        if medians[i] <= 0:
            break
        ans += medians[i]
    print(ans)

if __name__ == "__main__":
    main()

---

この解説は gpt-5.2-high によって生成されました。