#D. 顺手牵羊

    传统题 文件IO:shun 1000ms 256MiB

顺手牵羊

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

微隙在所必乘,微利在所必得。少阴,少阳。

题目描述

33DAI 进入了一个 nnnn 列的二维数组。数组中每个位置都有一只羊,第 ii 行第 jj 列的羊的重量是 ai,ja_{i,j}

33DAI 一开始在 a1,1a_{1,1} 的位置,每次可以往右一步或者往下一步。即可以从 ai,ja_{i,j} 走到 ai+1,ja_{i+1,j} 或者 ai,j+1a_{i,j+1}。但是不能走出这个数组,即不能走到下标小于 11 或大于 nn 的位置。他走到 an,na_{n,n} 就会停下。

他每次到达一个位置就会牵走那里的羊,显然最终他一共走了 2n12n-1 步,牵走了 2n12n-1 头羊。33DAI 会在这些羊中拿出最重的 kk 只羊送给 Kitten 作为她 10 月 9 日的生日礼物。他希望这些羊都足够重,他想知道所有牵羊方案中,哪种方案的最重的 kk 只羊中最轻的那只羊最重。

说人话就是,从 a1,1a_{1,1} 走到 an,na_{n,n},每次只能向右或者向下,求路径上的数中的第 kk 名最大是多少。

输入格式

两个数 n,kn,k

接下来 nn 行,每行 nn 个数,第 ii 行第 jj 列为 ai,ja_{i,j}

输出格式

输出第 kk 大的数最大是多少。

3 3
1 6 5
8 4 7
9 2 1
5

可以走 1->6->5->7->1 这条路,这样第 33 重的羊的重量是 55,其他方案都不如这个方案。

5 5
52 92 99 100 89
13 98 47 44 13
11 93 40 39 81
32 66 22 52 28
21 18 29 85 52
81
5 7
65 47 52 52 17
84 46 59 45 8
40 100 39 89 84
51 21 55 38 5
8 34 26 24 11
45

数据规模与约定

对于 100%100\% 的数据,1n10001 \le n \le 10001k2n11\le k\le 2n-11ai,j1091\le a_{i,j}\le 10^9

  • 子任务 1(10 分):保证所有 ai,ja_{i,j} 都相等。
  • 子任务 2(20 分):保证 k=1k=1
  • 子任务 3(30 分):保证 n=5n=5
  • 子任务 4(40 分):没有特殊限制。

挖土机 CSP-J 模拟赛 ~ 第九场

未参加
状态
已结束
规则
OI
题目
4
开始于
2024-10-1 4:00
结束于
2024-10-3 4:00
持续时间
3.5 小时
主持人
参赛人数
81