前半と後半の2つの部分にわけて問題を考えます。

前半パートは、各観光地の評価値を求めることです。
これは問題文の指示通り、各 \(i\) について、観光地 \(i\) のお土産の満足度をソートし、 \(\frac{C_i+1}{2}\) 番目の値を実際に確認することで求めることができます。

後半パートは、評価値がわかっている状態で訪れる観光地を適切に選ぶことです。
これは評価値の高い順に訪れるのが最適です。ただし、評価値が \(0\) 以上の観光地が \(K\) 個未満しか存在しないときに、評価値が負の観光地を訪れないように注意してください。評価値が負の観光地は最初から存在しないものとして扱うと、実装が比較的容易になります。

ソートがボトルネックとなり、\(C=\max C_i\) として、計算量は \(O(NC\log C+N\log N)\) となります。

実装例 (C++)

#include<bits/stdc++.h>
using namespace std;

int main(){
  int n, k;
  cin >> n >> k;

  vector<int> a;
  for(int i=0; i<n; i++){
    int c;
    cin >> c;
    vector<int> v(c);
    for(int j=0; j<c; j++) cin >> v[j];
    sort(v.begin(), v.end());
    if(v[c/2] > 0){
      a.push_back(v[c/2]);
    }
  }

  sort(a.rbegin(), a.rend());
  int ans = 0;
  for(int i=0; i<min((int)a.size(),k); i++){
    ans += a[i];
  }
  cout << ans << endl;
}

実装例 (Python)

N, K = map(int, input().split())

a = []
for _ in range(N):
  C = int(input())
  V = list(map(int, input().split()))
  V.sort()
  if V[C//2] > 0:
    a.append(V[C//2])

a.sort(reverse=True)
print(sum(a[:K]))
\