Overview

Given each student’s scores, the problem asks to select the top \(K\) students (including ties) from those who meet the minimum score threshold in all subjects, ranked by total score in descending order.

Analysis

In this problem, we first consider only students who meet the “minimum score threshold in all subjects” (qualified students). This can be determined by checking all subjects for each student.

Next, we calculate the total scores of the qualified students and sort them in descending order. However, there is a condition that in case of ties, students are ordered by student number in ascending order. Therefore, by using the sort key (-total_score, student_number), we can naturally satisfy this condition.

An additional point to note is that when selecting the top \(K\) students, all students who have the same score as the \(K\)-th student are also selected. For example, if \(K=3\) and the top 3 scores are [100, 90, 90], then all students with 90 points are selected. Therefore, we need to obtain the score of the \(K\)-th student and extract all students whose score is greater than or equal to that.

A naive approach of simply sorting everyone and taking the top \(K\) students may not handle the tie-breaking correctly, so score comparison is necessary.

Also, since \(M \leq 10\) according to the constraints, checking the qualification of each student and calculating total scores can be done efficiently.

Algorithm

1. For each student, determine whether they meet the minimum score threshold in all subjects, and list the qualified students.
2. For the qualified students, calculate the total score across all subjects and store it in the form (total_score, student_number).
3. Sort this list according to the following rules:
   • Descending order of total score (highest first)
   • If total scores are the same, ascending order of student number
4. After sorting, obtain the lowest score among the top \(K\) students.
5. Select all students whose score is greater than or equal to that score (including ties).
6. Output the selected student numbers in ascending order.

Complexity

• Time complexity: \(O(N \cdot M + N \log N)\)
  • Qualification check for each student takes \(O(M)\), for \(N\) students → \(O(N \cdot M)\)
  • Sorting takes \(O(N \log N)\)
• Space complexity: \(O(N + M)\)
  • Space needed for the threshold array \(T\) and the list of qualified students

Implementation Notes

• To handle ties, it is necessary to explicitly obtain the score of the \(K\)-th student and select all students with a score greater than or equal to it.

• By using the sort key (-score, id), we can simultaneously achieve descending order by score and ascending order by student number.

• By reading input efficiently, the solution can handle \(N\) up to \(10^5\) within the time limit.

  Source Code

import sys

# 入力の読み込み
input = sys.stdin.read
data = input().split()

idx = 0
N = int(data[idx])
idx += 1
M = int(data[idx])
idx += 1
K = int(data[idx])
idx += 1

# 基準点の読み込み
T = list(map(int, data[idx:idx+M]))
idx += M

# 学生データの読み込み
students = []
for i in range(N):
    scores = list(map(int, data[idx:idx+M]))
    idx += M
    # 基準通過判定
    passed = all(scores[j] >= T[j] for j in range(M))
    if passed:
        total = sum(scores)
        students.append((total, i + 1))  # (合計点, 学生番号)

# 合計点の降順、学生番号の昇順でソート
students.sort(key=lambda x: (-x[0], x[1]))

# 上位K人の合計点を取得（K番目と同じ点数の人も含む）
if not students:
    exit()

# K番目の合計点を取得
k_th_score = students[min(K, len(students)) - 1][0]

# K番目と同じ点数以上の学生をすべて選ぶ
recipients = [student[1] for student in students if student[0] >= k_th_score]

# 昇順にソートして出力
recipients.sort()
for num in recipients:
    print(num)

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