A21665.小凸玩矩阵

省选/NOI-

通过率:0%

时间限制:1.00s

内存限制:128MB

题目描述

小凸和小方是好朋友,小方给了小凸一个 nn × mm (nm)(n \leq m) 的矩阵 AA,并且要求小凸从矩阵中选出 nn 个数,其中任意两个数都不能在同一行或者同一列。现在小凸想知道,选出的 nn 个数中第 kk 大的数的最小值是多少。

输入格式

11 行读入 33 个整数 n,m,kn, m, k

接下来 nn 行,每一行有 mm 个数字,第 ii 行第 jj 个数字代表矩阵中第 ii 行第 jj 列的元素 Ai,jA_{i,j}

输出格式

输出包含一行,为选出的 nn 个数中第 kk 大数的最小值。

输入输出样例

  • 输入#1

    2 3 1
    1 2 4
    2 4 1

    输出#1

    1
  • 输入#2

    3 4 2
    1 5 6 6
    8 3 4 3
    6 8 6 3

    输出#2

    3

说明/提示

对于 2020% 的数据, 1nm91 \leq n \leq m \leq 9

对于 4040% 的数据, 1nm22,1n121 \leq n \leq m \leq 22, 1 \leq n \leq 12

对于 100100% 的数据, 1knm250,1Ai,j1091 \leq k \leq n \leq m \leq 250, 1 \leq A_{i,j} \leq 10^9

首页