Overview

This problem asks us to verify whether each student’s scores in all subjects meet the minimum threshold, then from the students who satisfy the condition, select the top K students by total score across all subjects (including all students tied at the K-th position), and output their student numbers in ascending order.

Analysis

In this problem, we first need to check whether each student scores at or above the minimum threshold \(T_j\) in every subject. Only students who meet the threshold in all subjects become “qualifying students.” Next, we select from the qualifying students in descending order of total score, with the following two key points:

1. Efficient Filtering: Since we check each student’s scores across all subjects (at most 10 subjects), this can be processed in \(O(NM)\). With \(N\) up to \(10^5\) and \(M\) up to 10, \(10^6\) comparisons are more than sufficient.

2. Tie Handling: After sorting by total score and selecting the top K students, if there are multiple students with the same score as the K-th ranked student, all of them must be included. Simply taking the top K students is insufficient — properly including tied students is crucial.

Algorithm

1. Read Input: Read the number of students \(N\), number of subjects \(M\), number of students to select \(K\), the threshold score \(T_j\) for each subject, and each student’s scores.
2. Select Qualifying Students: For each student, check whether their scores in all subjects meet or exceed the thresholds. For students who satisfy the condition, record their total score and student number.
3. Sort: Sort the qualifying students in descending order of total score (and ascending order of student number in case of ties).
4. Selection: Select the top K students, but also include any students with the same score as the K-th ranked student. Specifically, from the beginning of the sorted list, select all students whose total score is greater than or equal to the K-th ranked student’s score.
5. Output: Output the selected student numbers in ascending order.

Complexity

• Time Complexity: \(O(NM + N \log N)\)
  • Checking qualifying students takes \(O(NM)\)
  • Sorting takes \(O(N \log N)\)
  • Since \(M\) is at most 10, which is small, \(O(N \log N)\) is effectively the dominant term.
• Space Complexity: \(O(N)\)
  • A list is needed to store the student data.

Implementation Notes

• Early break: During the threshold check, if even one subject is below the threshold, immediately stop processing that student to avoid unnecessary computation.

• Tie handling: After sorting, use the K-th ranked student’s score as a cutoff and select all students with scores at or above that value — this makes it easy to include tied students.

• Efficient input processing: Reading large amounts of input data at once reduces I/O overhead.

  Source Code

import sys

def main():
    data = sys.stdin.read().split()
    if not data:
        return
    
    n = int(data[0])
    m = int(data[1])
    k = int(data[2])
    
    T = list(map(int, data[3:3+m]))
    
    students = []
    index = 3 + m
    for i in range(n):
        scores = list(map(int, data[index:index+m]))
        index += m
        students.append((i+1, scores))
    
    qualified = []
    for idx, scores in students:
        valid = True
        total = 0
        for j in range(m):
            if scores[j] < T[j]:
                valid = False
                break
            total += scores[j]
        
        if valid:
            qualified.append((total, idx))
    
    if not qualified:
        return
    
    qualified.sort(key=lambda x: (-x[0], x[1]))
    
    result = []
    if k >= len(qualified):
        result = [idx for _, idx in qualified]
    else:
        kth_score = qualified[k-1][0]
        for total, idx in qualified:
            if total >= kth_score:
                result.append(idx)
            else:
                break
    
    result.sort()
    for idx in result:
        print(idx)

if __name__ == "__main__":
    main()

This editorial was generated by deepseekv3.