Overview

This is a problem where you calculate the median (evaluation value) from the satisfaction scores of souvenirs at each tourist spot, and find the maximum possible sum of evaluation values when selecting up to \(K\) tourist spots with the highest evaluation values.

Analysis

To solve this problem, it is helpful to break it down into the following two steps.

1. Calculate the evaluation value for each tourist spot As stated in the problem, the evaluation value of each tourist spot is the median of the souvenir satisfaction scores. To find the median, sort the satisfaction scores in ascending order and take the middle value. Since the number of souvenirs \(C_i\) is always odd, when using 0-based indexing (0-indexed) in programming, the median is the element at index C_i // 2.

2. Maximize the sum of evaluation values Once the evaluation value for each tourist spot is determined, the next step is to decide which tourist spots to select. To maximize the sum of evaluation values, the following two points must be considered: - Prioritize selecting tourist spots with higher evaluation values - Do not select tourist spots with negative (or \(0\)) evaluation values

You can select “from \(0\) up to \(K\) tourist spots.” If you select a tourist spot with a negative evaluation value, the total sum decreases. Therefore, the optimal strategy is to consider only tourist spots with positive evaluation values and select up to \(K\) spots in descending order of their values.

Algorithm

1. For each tourist spot \(i\), sort the list of souvenir satisfaction scores \(V_{i,j}\) in ascending order.
2. Take the element at index C_i // 2 of the sorted list as the evaluation value of tourist spot \(i\).
3. Once the evaluation values of all tourist spots are computed, sort them in descending order.
4. Check up to \(K\) values from the beginning of the descending sorted evaluation values, and add to the answer (total sum) only if the value is greater than \(0\) (i.e., positive).
5. Output the final total sum.

Complexity

• Time complexity: \(O(\sum (C_i \log C_i) + N \log N)\) Sorting the souvenirs for each tourist spot takes \(O(C_i \log C_i)\), and sorting the evaluation values of \(N\) tourist spots takes \(O(N \log N)\). Since the constraints (\(N \leq 100\), \(C_i \leq 99\)) are very small, this easily fits within the time limit.
• Space complexity: \(O(N + \max(C_i))\) The array holding the evaluation values for each tourist spot uses \(O(N)\), and the array holding the souvenir satisfaction scores during input uses at most \(O(\max(C_i))\) memory.

Implementation Notes

• Median index: In 0-indexed languages such as Python, when the number of elements C is odd, the median index can be easily obtained with C // 2 (floor division). For example, when C = 5, the indices are 0, 1, 2, 3, 4, and the median is at index 2 (5 // 2).

• Add only positive values: Since the problem states “0 or more spots,” when all evaluation values are negative, selecting 0 spots (total of \(0\)) is the correct answer. This can be handled correctly by adding a conditional branch if evaluations[i] > 0: inside the loop.

  Source Code

import sys

def solve():
    input = sys.stdin.read
    data = input().split()
    if not data:
        return
    
    N = int(data[0])
    K = int(data[1])
    
    idx = 2
    evaluations = []
    for _ in range(N):
        C_i = int(data[idx])
        idx += 1
        V_i = [int(x) for x in data[idx : idx + C_i]]
        idx += C_i
        
        V_i.sort()
        median = V_i[C_i // 2]
        evaluations.append(median)
        
    evaluations.sort(reverse=True)
    
    ans = 0
    for i in range(min(K, N)):
        if evaluations[i] > 0:
            ans += evaluations[i]
            
    print(ans)

if __name__ == '__main__':
    solve()

---

This editorial was generated by gemini-3.1-pro-thinking.