Overview

This problem asks you to compute the “rating (the median of souvenir satisfaction values)” for each tourist spot, then select up to \(K\) spots with positive ratings to maximize the total.

Analysis

Key Observation ①: The rating is the median

The rating of each tourist spot \(i\) is the \(\frac{C_i+1}{2}\)-th value when the satisfaction values of the \(C_i\) souvenirs are sorted in ascending order — in other words, the median. Since \(C_i\) is always odd, the median is uniquely determined.

Example: If the souvenir satisfaction values are \([3, -1, 5]\), sorting in ascending order gives \([-1, 3, 5]\), and the median (the 2nd value) is \(3\).

Key Observation ②: Greedily selecting positive ratings is optimal

• Since you can choose between 0 and \(K\) spots inclusive, not visiting any spot is also an option.
• Visiting a spot with a negative rating decreases the total, so you should only select spots with positive ratings.
• Spots with a rating of 0 do not affect the total whether selected or not (so you don’t need to select them).
• If there are \(K\) or more spots with positive ratings, select the top \(K\) largest ones. If there are fewer than \(K\), select all spots with positive ratings.

Comparison with a naive approach

Trying all combinations of choosing 0 to \(K\) spots from \(N\) would require up to \(2^N\) possibilities in the worst case, which is far too slow for \(N=100\). However, with the greedy approach described above, you can obtain the optimal solution simply by sorting and taking the top values.

Algorithm

1. For each tourist spot \(i\), sort the \(C_i\) satisfaction values in ascending order and find the median (the element at index \(C_i // 2\)).
2. From all the medians, collect only the positive ones (\(> 0\)).
3. Sort the collected positive medians in descending order and compute the sum of up to the first \(K\) values.
4. That sum is the answer (if there are no positive medians, the answer is \(0\)).

Example: For \(N=3, K=2\), if the ratings of each tourist spot are \([5, -3, 2]\), the positive ratings are \([5, 2]\). Since you can select up to \(K=2\) spots, you select both for a total of \(7\) as the answer.

Complexity

• Time complexity: \(O\!\left(\sum_{i=1}^{N} C_i \log C_i + N \log N\right)\)
  • This is the sum of the cost of sorting souvenirs for each tourist spot \(O(C_i \log C_i)\) and the cost of sorting the medians \(O(N \log N)\).
• Space complexity: \(O\!\left(\max_i C_i + N\right)\)
  • This is needed to store the souvenir list for each tourist spot and the list of medians.

Implementation Notes

• Median index: When the \(C_i\) elements are sorted in ascending order using 0-indexed notation, the median is V[C_i // 2]. For example, if \(C_i = 5\), it is V[2] (the 3rd element).

• Don’t forget the case of selecting 0 spots: If all ratings are negative, visiting no spots yields a maximum total of \(0\). By collecting only positive ratings, this case naturally results in a total of \(0\).

• Spots with a rating of 0: Since selecting them does not change the total, filtering them out with m > 0 in the implementation causes no issues.

  Source Code

import sys

def main():
    input_data = sys.stdin.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    K = int(input_data[idx]); idx += 1
    
    medians = []
    for i in range(N):
        C = int(input_data[idx]); idx += 1
        V = []
        for j in range(C):
            V.append(int(input_data[idx])); idx += 1
        V.sort()
        median = V[C // 2]
        medians.append(median)
    
    # Select up to K spots with positive medians to maximize sum
    positive_medians = sorted([m for m in medians if m > 0], reverse=True)
    result = sum(positive_medians[:K])
    print(result)

main()

This editorial was generated by claude4.6opus-thinking.