Overview

From \(N\) students, extract “qualifying students” who meet the minimum threshold score in every subject, then identify the top \(K\) students by total score (including all students tied with the \(K\)-th place score).

Approach

To solve this problem, you need to process the following three steps in order:

1. Filtering Qualifying Students For each student, check whether \(S_{i,j} \geq T_j\) holds for all subjects \(j\). If even one subject falls below the threshold, that student is excluded from consideration. At this stage, save the “total score” and “student number” as a pair for later ranking.
2. Ranking by Total Score Sort the qualifying students in descending order of total score.
3. Determining Recipients and Handling Ties Pay attention to the condition: “All students tied with the \(K\)-th place total score are also recipients.”
   • If there are \(K\) or fewer qualifying students, all of them become recipients.
   • If there are more than \(K\) qualifying students, first check the score of the \(K\)-th person in the descending sorted list (the boundary value). Then extract all students with a score greater than or equal to this boundary value as recipients.

Finally, sort the student numbers of the recipients in ascending order (smallest number first) and output them.

Algorithm

1. Store the minimum threshold scores \(T_1, \dots, T_M\) in an array.
2. For each student \(i = 1, \dots, N\), do the following:
   • Read the scores \(S_{i,j}\) for each subject and calculate the total score total_score.
   • Determine whether \(S_{i,j} \geq T_j\) holds for all \(j\).
   • Only if the condition is satisfied, add (total_score, i) to the list passers.
3. Sort passers in descending order of total_score.
4. Create the list of recipients result_ids:
   • If the number of elements in passers is \(K\) or fewer, add all student numbers.
   • If there are more than \(K\), set threshold to the total score of passers[K-1] (the \(K\)-th highest), and add the numbers of all students whose total score is greater than or equal to threshold.
5. Sort result_ids in ascending order and output one per line.

Complexity

• Time complexity: \(O(NM + N \log N)\)
  • Checking scores for all students takes \(O(NM)\).
  • Sorting the qualifying students takes at most \(O(N \log N)\).
  • Since \(N=10^5, M=10\), the total number of operations is approximately \(10^6\), which comfortably fits within the time limit.
• Space complexity: \(O(NM)\) or \(O(N)\)
  • Storing the input data requires \(O(NM)\), and the list managing qualifying students uses \(O(N)\) memory.

Implementation Notes

• Fast I/O: Since \(N\) can be as large as \(10^5\), in Python it is faster to read all input at once using sys.stdin.read().split() rather than calling input() repeatedly.

• Sort Key: When sorting in descending order of total score, using Python’s sort(key=..., reverse=True) allows for concise code.

• Output Order: Note that after selecting students by score ranking, you need to re-sort by “student number” before outputting.

  Source Code

import sys

def solve():
    # Use sys.stdin.read().split() to read all input tokens at once for speed.
    # This approach is generally more efficient for large inputs in Python.
    try:
        input_data = sys.stdin.read().split()
        if not input_data:
            return
        # Convert all tokens to integers.
        data = list(map(int, input_data))
    except (EOFError, ValueError):
        return

    # Basic parameters: N (number of students), M (number of subjects), K (recipient limit).
    if len(data) < 3:
        return
    N, M, K = data[0], data[1], data[2]
    
    # Minimum criteria points for each of the M subjects.
    if len(data) < 3 + M:
        return
    T = data[3 : 3 + M]
    
    passers = []
    # Student data starts from index 3 + M.
    # Each student has exactly M scores in the input.
    current_idx = 3 + M
    
    for i in range(1, N + 1):
        # Ensure we have enough data to read M scores for the student.
        if current_idx + M > len(data):
            break
            
        is_ok = True
        total_score = 0
        # Check if the student meets the minimum criterion for every subject.
        for j in range(M):
            score = data[current_idx + j]
            if score < T[j]:
                is_ok = False
            total_score += score
        
        # If the student meets all criteria, they are added to the list of "criteria passers".
        if is_ok:
            passers.append((total_score, i))
        
        # Move the index to the next student's data.
        current_idx += M
        
    # If no students passed the criteria, there are no recipients.
    if not passers:
        return
        
    # Sort the passers by their total score in descending order.
    # Python's sort is stable, which is helpful but not strictly required here.
    passers.sort(key=lambda x: x[0], reverse=True)
    
    # Determine the recipients based on the selection criteria.
    if len(passers) <= K:
        # If there are K or fewer passers, everyone who passed is a recipient.
        result_ids = [p[1] for p in passers]
    else:
        # If there are more than K passers, identify the score of the K-th person.
        # Since passers is 0-indexed, the K-th person is at index K-1.
        threshold_score = passers[K-1][0]
        # All passers with a total score greater than or equal to the K-th score are recipients.
        result_ids = [p[1] for p in passers if p[0] >= threshold_score]
        
    # The problem requires the student IDs of recipients to be output in ascending order.
    result_ids.sort()
    
    # Output the student IDs, one per line.
    if result_ids:
        sys.stdout.write('\n'.join(map(str, result_ids)) + '\n')

if __name__ == '__main__':
    solve()

This editorial was generated by gemini-3-flash-thinking.