Overview

Given the evaluation value of each tourist spot (the median of souvenir satisfaction ratings), the problem asks to select at most K tourist spots to maximize the total evaluation value.

Analysis

The key observations are as follows: 1. The evaluation value of each tourist spot can be computed as the median of the sorted souvenir satisfaction ratings for that spot 2. It is optimal to select only tourist spots with positive evaluation values (since adding negative values would decrease the total) 3. The total can be maximized by selecting tourist spots in order of decreasing evaluation value

A naive approach of trying all combinations exists, but since N can be up to 100 and K can be up to 100, the number of combinations becomes enormous and is not practical. Instead, we can solve this efficiently using a greedy approach.

Algorithm

1. For each tourist spot, sort the souvenir satisfaction ratings and compute the median
2. Sort the obtained evaluation values in descending order (from largest to smallest)
3. Sum only the positive values among the top K evaluation values
4. If a negative value is encountered along the way, do not add it or any subsequent values (since adding negative values would decrease the total)

Complexity

• Time complexity: \(O(N \cdot C_i \log C_i)\)
  • The sorting process for each tourist spot is dominant (\(C_i \leq 99\))
• Space complexity: \(O(N)\)
  • Only an array for storing evaluation values is used

Implementation Notes

• For computing the median, take the \((C_i + 1)/2\)-th value (subtract 1 since indexing is 0-based)

• The optimal solution is obtained by selecting only evaluation values that are positive

• Do not forget to handle the case of empty input (0 tourist spots)

  Source Code

def main():
    import sys
    data = sys.stdin.read().splitlines()
    if not data:
        print(0)
        return
        
    first_line = data[0].split()
    N = int(first_line[0])
    K = int(first_line[1])
    
    attractions = []
    index = 1
    for i in range(N):
        C = int(data[index]); index += 1
        values = list(map(int, data[index].split())); index += 1
        values.sort()
        median_index = (C + 1) // 2 - 1
        median = values[median_index]
        attractions.append(median)
    
    attractions.sort(reverse=True)
    total = 0
    for i in range(min(K, len(attractions))):
        if attractions[i] > 0:
            total += attractions[i]
        else:
            break
            
    print(total)

if __name__ == "__main__":
    main()

This editorial was generated by deepseekv3.