Overview

For each tourist spot, compute the median of souvenir satisfaction values (the “rating”), then select up to \(K\) spots with high ratings to maximize the total sum of ratings.

Analysis

In this problem, we need to compute the “rating” for each tourist spot. The rating is the median of the satisfaction values of souvenirs sold at that spot — specifically, the \(\frac{C_i + 1}{2}\)-th value (or the \(\frac{C_i - 1}{2}\)-th value in 0-indexed) when the satisfaction list is sorted.

For example, suppose a tourist spot has souvenir satisfaction values [3, -1, 2]. Sorting gives [-1, 2, 3], so the median (rating) is 2.

After computing the rating for every tourist spot, the optimal strategy is to select “the top \(K\) spots with positive ratings.” There is no benefit in choosing a negative rating, and choosing 0 does not contribute to the total sum, so it is best to select only positive ratings, taking at most \(K\) of them.

This straightforward approach is sufficiently fast, and there are no particular traps that would cause TLE or WA. However, it is necessary to read the input efficiently.

Algorithm

1. For each tourist spot:
   • Read the satisfaction list \(V\) and sort it.
   • Obtain the median as the \((C_i - 1)/2\)-th element and use it as the rating.
2. Collect all ratings and sort them in descending order.
3. Sum the top \(K\) positive values to get the answer (stop early if a value becomes negative).

Complexity

• Time complexity: \(O(N \cdot C_{\text{max}} \log C_{\text{max}} + N \log N)\)
  • Computing the median for each tourist spot takes \(O(C_i \log C_i)\), done \(N\) times.
  • Sorting the ratings takes \(O(N \log N)\).
• Space complexity: \(O(C_{\text{max}} + N)\)
  • For storing each tourist spot’s \(V\) and the list of ratings.

Implementation Notes

• Use sys.stdin.read to read standard input efficiently.

• The median index is (C - 1) // 2 in 0-indexed.

• Since negative ratings should not be selected, greedily pick only positive values from the top after sorting.

  Source Code

import sys
import heapq

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    idx = 0
    N = int(data[idx])
    idx += 1
    K = int(data[idx])
    idx += 1
    
    evaluations = []
    
    for _ in range(N):
        C = int(data[idx])
        idx += 1
        V = []
        for _ in range(C):
            V.append(int(data[idx]))
            idx += 1
        V.sort()
        median = V[(C - 1) // 2]
        evaluations.append(median)
    
    # Sort evaluations in descending order to pick the top K positive ones
    evaluations.sort(reverse=True)
    
    max_sum = 0
    for i in range(min(K, len(evaluations))):
        if evaluations[i] > 0:
            max_sum += evaluations[i]
        else:
            break
    
    print(max_sum)

if __name__ == "__main__":
    main()

This editorial was generated by qwen3-coder-480b.