Overview

For each player, calculate the “final score” as the total score minus one highest and one lowest score, then find the player number with the highest final score (smallest number in case of ties).

Analysis

The final score is “the sum of the remaining scores after excluding the highest and lowest scores.” If you try to implement this directly by sorting the scores each time, it costs \(O(M \log M)\) per player, resulting in \(O(NM \log M)\) overall, which is wasteful.

The key insight here is that since we only need to exclude one maximum and one minimum, sorting is unnecessary.

For each player’s score sequence \(S_{i,1},\dots,S_{i,M}\): - Sum \(s=\sum_j S_{i,j}\) - Minimum \(mn=\min_j S_{i,j}\) - Maximum \(mx=\max_j S_{i,j}\)

can all be computed in a single pass, and the final score is simply: $\( score = s - mn - mx \)$

Also, when there are ties, we need to choose the player with the smallest number. By setting the update condition to “update only when \(score\) is strictly greater,” the first player encountered with the maximum score (= the one with the smallest number) is retained.

(Example) If the scores are [10, 3, 7, 8], the sum is \(28\), the minimum is \(3\), and the maximum is \(10\), so the final score is \(28-3-10=15\).

Algorithm

1. Prepare variables best_score (the maximum final score so far) and best_idx (that player’s number).
2. For each player \(i=1..N\):
   1. Initialize s=0, mn=101, mx=0 (since scores range from \(1..100\), these initial values are safe).
   2. While reading the \(M\) scores, add each to s and update mn and mx.
   3. Compute score = s - mn - mx.
   4. If score > best_score, update best_score=score, best_idx=i (do not update on ties).
3. Output best_idx.

Complexity

• Time complexity: \(O(NM)\) (each score is examined exactly once)
• Space complexity: \(O(1)\) (only the sum, minimum, and maximum are maintained for each player; the entire input is not stored in an array)

Implementation Notes

• No sorting: Since we only need the sum, minimum, and maximum, a single pass is sufficient.

• Tie-breaking: By using only > as the update condition, in case of ties, the player who appeared first (with the smaller number) is selected.

• Fast input: Since the constraint \(N \times M \le 10^6\) is fairly large, in Python it is more stable to use sys.stdin.buffer.read() with an integer parser (like the int_reader in the provided code) for fast reading.

  Source Code

import sys

def int_reader():
    data = sys.stdin.buffer.read()
    n = len(data)
    i = 0
    while i < n:
        while i < n and data[i] <= 32:
            i += 1
        if i >= n:
            break
        num = 0
        while i < n and data[i] > 32:
            num = num * 10 + (data[i] - 48)
            i += 1
        yield num

it = int_reader()
N = next(it)
M = next(it)

best_score = -10**18
best_idx = 1

for idx in range(1, N + 1):
    s = 0
    mn = 101
    mx = 0
    for _ in range(M):
        x = next(it)
        s += x
        if x < mn:
            mn = x
        if x > mx:
            mx = x
    score = s - mn - mx
    if score > best_score:
        best_score = score
        best_idx = idx

sys.stdout.write(str(best_idx))

---

This editorial was generated by gpt-5.2-high.