Overview

\(N\) contestants are each scored by \(M\) judges. For each contestant, the final score is the sum of the remaining scores after removing the highest and lowest scores. Find the number of the contestant with the highest final score.

Analysis

For this problem, we need to perform the following operations for each contestant: 1. Remove one maximum value and one minimum value from the \(M\) scores. 2. Calculate the sum of the remaining \(M - 2\) scores.

A straightforward approach would be to sort each time and remove the first and last elements, giving a time complexity of \(O(M \log M)\) per contestant, and \(O(N \cdot M \log M)\) overall. Since the constraint is \(N \times M \leq 10^6\), this could result in TLE in the worst case when \(M\) is large.

However, we can actually handle this without sorting by simply subtracting the maximum and minimum values. That is, by subtracting the maximum and minimum from the total sum of all scores, we obtain the desired “remaining sum.” This allows us to process each contestant in \(O(M)\), resulting in \(O(N \cdot M)\) overall.

Also, note that in the case of a tie, we need to select the contestant with the smallest number. By handling this comparison appropriately, we can obtain the correct answer.

Algorithm

1. For each contestant, receive the list of scores.
2. Calculate the sum, maximum, and minimum of that list.
3. Calculate the final score = sum - maximum - minimum.
4. Compare with the current best score, and update if it is higher. In case of a tie, choose the contestant with the smaller number.
5. After checking all contestants, output the number of the contestant with the highest score.

Example

For example, if contestant 1’s scores are [90, 85, 95, 80]: - Sum: \(90 + 85 + 95 + 80 = 350\) - Maximum: \(95\) - Minimum: \(80\) - Final score: \(350 - 95 - 80 = 175\)

Complexity

• Time complexity: \(O(N \cdot M)\)
• Space complexity: \(O(N \cdot M)\) (due to the array holding the input)

Implementation Notes

• Since the input is large, sys.stdin.read is used for faster input.
• By reading each contestant’s scores all at once and managing them as a list, processing can be done efficiently.
• Be careful about handling contestant numbers in case of ties when comparing final scores.

## Source Code

```python
import sys
input = sys.stdin.read

def main():
    data = input().split()
    N = int(data[0])
    M = int(data[1])
    scores = []
    index = 2
    for i in range(N):
        player_scores = list(map(int, data[index:index+M]))
        index += M
        scores.append(player_scores)
    
    max_score = -1
    winner = -1
    
    for i in range(N):
        s_list = scores[i]
        total = sum(s_list)
        max_s = max(s_list)
        min_s = min(s_list)
        final_score = total - max_s - min_s
        
        if final_score > max_score:
            max_score = final_score
            winner = i + 1
        elif final_score == max_score and (winner == -1 or i + 1 < winner):
            winner = i + 1
            
    print(winner)

if __name__ == "__main__":
    main()

---

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