Overview

Given \(N\) students, we need to select “qualifying students” who meet the minimum threshold score in every subject, and then find the top \(K\) students by total score among them (including all students tied at the cutoff).

Analysis

This problem can be broken down into three major steps:

1. Filtering qualifying students: For each student, determine whether they score at least the minimum threshold \(T_j\) in every subject.
2. Sorting by total score: Sort the qualifying students in descending order of their total score across all subjects.
3. Selecting the top \(K\) students (handling ties): Include all students who have the same total score as the student ranked \(K\)-th.

Even a straightforward approach only requires checking \(M\) subjects for each of the \(N\) students, resulting in \(O(NM)\) time. Since \(N \leq 10^5\) and \(M \leq 10\), the computation is at most around \(10^6\), which is fast enough without any special optimization.

Tie-breaking is the only point requiring careful attention. For example, if there are 10 qualifying students and \(K = 3\), and the 3rd and 4th students in descending order of total score are tied, then the 4th student is also included as a recipient. Specifically, we take the total score of the \(K\)-th student as the “borderline (threshold)” and select all qualifying students whose total score is at or above that threshold.

Algorithm

1. Read the input and obtain the minimum threshold array \(T\).
2. For each student \(i\) (\(1 \leq i \leq N\)):
   • Check whether \(S_{i,j} \geq T_j\) holds for every subject \(j\).
   • If so, add the pair of total score \(\text{total} = \sum_{j} S_{i,j}\) and student number \(i\) to a list.
3. If there are 0 qualifying students, output nothing and terminate.
4. Sort the list in descending order of total score.
5. If there are \(K\) or fewer qualifying students, all of them become recipients.
6. If there are more than \(K\), set the total score of the \(K\)-th student (index \(K-1\) in 0-indexed) as the threshold \(\text{threshold}\), and select all students whose total score is at least \(\text{threshold}\).
7. Sort the recipient student numbers in ascending order and output them.

Concrete example: With \(N=5\), \(M=2\), \(K=2\), \(T=[50, 50]\), suppose the qualifying students’ total scores are \((300, 250, 250, 200)\). The \(K=2\)nd total score is \(250\). There are 3 students with a total score of \(250\) or above, so all 3 become recipients.

Complexity

• Time complexity: \(O(NM + N \log N)\)
  • \(O(NM)\) for checking thresholds and computing total scores for each student
  • \(O(N \log N)\) for sorting (in the worst case where all students are qualifying)
• Space complexity: \(O(NM)\)
  • For storing the input data and the list of qualifying students

Implementation Notes

• Fast input: By reading all input at once with sys.stdin.read() and splitting with split(), this is faster than repeatedly calling input() (effective when \(N\) is large).

• Selection by threshold: After sorting, store the \(K\)-th value as the threshold and use a list comprehension for batch filtering, which makes tie-breaking simple to implement.

• Output order: The problem requires output in “ascending order of student numbers,” so don’t forget to sort the recipient list one more time at the end.

  Source Code

import sys

def main():
    input_data = sys.stdin.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    M = int(input_data[idx]); idx += 1
    K = int(input_data[idx]); idx += 1
    
    T = [int(input_data[idx + j]) for j in range(M)]
    idx += M
    
    passed = []
    for i in range(1, N + 1):
        scores = [int(input_data[idx + j]) for j in range(M)]
        idx += M
        if all(scores[j] >= T[j] for j in range(M)):
            total = sum(scores)
            passed.append((total, i))
    
    if not passed:
        return
    
    passed.sort(key=lambda x: -x[0])
    
    if len(passed) <= K:
        recipients = [p[1] for p in passed]
    else:
        threshold = passed[K - 1][0]
        recipients = [p[1] for p in passed if p[0] >= threshold]
    
    recipients.sort()
    print('\n'.join(map(str, recipients)))

main()

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