← 返回题目列表

AtCoder · awc0059_b

B. 奖学金评选

中文机器翻译题面 查看原题

分数: 300 分

问题陈述

高桥作为学校奖学金评选委员会的成员,被指派负责确定今年的奖学金获得者。

今年, N 学生已申请奖学金,每个学生都被分配了一个编号 1 to N。选择评估等级(分数) M 科目,学生所在位置 i的科目成绩 j is S_{i,j} 点。

此外,每个科目 j 有最低阈值分数 T_j。奖学金获得者按照以下程序确定。

第 1 步:确定合格学生

学生 i 如果满足以下条件,则被称为“合格学生” S_{i,j} \geq T_j 为 全部 科目 j (1 \leq j \leq M).

第 2 步:确定收件人

收件人根据符合条件的学生人数确定,如下。在这里, K 是作为选择配额给出的正整数。

  • 如果符合资格的学生人数为 K 或更少,所有符合条件的学生都成为受益人。特别是,如果有 0 符合条件的学生,则有 0 收件人。
  • 如果符合资格的学生人数超过 K,收件人选择如下。对于每个符合资格的学生 i,计算所有科目的总分 \displaystyle P_i = \sum_{j=1}^{M} S_{i,j}。排序 P_i 所有符合条件的学生的值按降序排列,并让 K从顶部开始的第一个值是边界线 B (因为有超过 K 符合资格的学生, K-第一个值始终存在)。所有符合资格的学生 P_i \geq B 成为收件人。

> 注意: 如果多个合格学生的总成绩与边界线相同 B,收件人数量可能超过 K.

代表 Takahashi 确定收件人的学生编号。

约束

  • 1 \leq N \leq 10^5
  • 1 \leq M \leq 10
  • 1 \leq K \leq N
  • 0 \leq T_j \leq 1000 (1 \leq j \leq M)
  • 0 \leq S_{i,j} \leq 1000 (1 \leq i \leq N, 1 \leq j \leq M)
  • 所有输入值均为整数。

输入

N M K
T_1 T_2 \ldots T_M
S_{1,1} S_{1,2} \ldots S_{1,M}
S_{2,1} S_{2,2} \ldots S_{2,M}
\vdots
S_{N,1} S_{N,2} \ldots S_{N,M}
  • 第一行包含三个空格分隔的整数: N 代表申请学生人数, M 代表受试者数量,以及 K 代表选拔名额。
  • 第二行包含空格分隔的整数 T_1, T_2, \ldots, T_M 代表每个科目的最低阈值分数。
  • 以下 N 行(来自行 3 转线 N + 2) 给出每个学生的分数。
  • 的 (2 + i)- 第行包含空格分隔的整数 S_{i,1}, S_{i,2}, \ldots, S_{i,M} 代表学生 i每个科目的分数。

输出

按升序输出收件人的学号,每行一个。如果有 0 收件人,什么也不输出(空输出)。


样本输入 1

5 3 2
50 60 55
80 70 60
40 80 70
90 65 80
55 60 55
70 75 90

示例输出 1

3
5

示例输入 2

8 2 3
30 30
50 50
80 90
40 60
70 80
20 90
60 90
90 80
35 65

示例输出 2

2
4
6
7

示例输入 3

10 4 5
70 65 60 75
80 70 65 80
50 90 80 70
75 68 62 90
60 65 70 80
90 80 75 85
72 66 61 76
30 40 50 60
85 70 60 80
70 65 60 74
95 85 80 90

示例输出 3

1
3
5
8
10