#G. G. ‘Riliane Lucifen d’Autriche’ teafrogsf 和他的四面镜子

    Type: Default 1000ms 512MiB

G. ‘Riliane Lucifen d’Autriche’ teafrogsf 和他的四面镜子

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

巴利索尔的儿子是独生子
身为富裕家庭的后代
任谁都羡慕的美少年
但他却有些地方不对劲
不但非常喜欢玩娃娃
总是只穿女孩子的衣服
还从母亲的房间里偷出用具
偷偷地化妆
周遭的人们都疏远着这样的他
所以他不论何时
都孤单一人
[1]

题目描述

在 knb 的形而上学数据库被击毁之后,OIER[2] 小队在这个信息屏蔽密度极高的时代彻底成为了视障者。但这一刻,蛙终于揭露了他四面镜子的真正力量:他的四面镜子中居然蕴含了 Ackermann(4,4)Ackermann(4,4) 个可以存储单位信息的结点,且它们之间均互相链接。而 knb 数据库的全部信息也被存储在他的镜子里。尽管这面镜子已经失去了它曾经的力量,没有了穿梭在其中的寄生之魂用于分析和处理信息[3],但现在他们已经看到了撬动败局的希望。

在众人的不懈努力下,他们找到了 nn 个相对重要的结点,它们的价值程度分别是 valival_i。他们打算在其中选择 mm 个结点,而通过拼接它们便能够获得有效信息,信息的价值是这mm个结点的价值之和。

由于每份信息都是独一无二的,他们打算先获得前 kk 个最重要的信息。作为 knb 和蛙共同开发(knb 负责开发,蛙负责提出 feature)的新智能,你必须计算出这 kk 个方案中价值最小的信息的价值。

数据格式与约定

输入

输入第一行包含三个正整数 n,m,k(1mn106,1k106)n,m,k(1 \le m\le n \le 10^6,1\le k\le 10^6),分别表示找到的结点,需要选择的结点个数,需要获得的信息个数。

接下来一行包含 nn 个整数 $val_1,val_2,\dots,val_n(\forall i, 1 \le val_i \le 10^9)$,表示每个结点的价值。

输出

输出包含一行一个整数 ansans,即价值最小的信息的价值。如果有多种选择信息的方案,任选一种即可。

如果 kk 比所有信息的数量都要大,输出 1-1

样例

3 2 2
1 2 3
4

样例解释

OIER 小队选取的两个方案按价值从小到大排序分别为:结点 11 和结点 33,价值为 44;结点 22 和结点 33,价值为 55

后记

“呼......总算搞定了。”

“好耶!”

OIER 小队的所有人都舒了一口气。数据库的恢复让他们燃起了最后的希望。

“这镜子恁牛啊。诶蛙你不是说过像这样的镜子一样的物件一共有七件吗?你咋只拿到了一件捏?”

“那都是人家的,能送我一件已经不错了,感觉这次纯属脸比较好。但是如果我们还想真正翻盘的话——”

“——就得看你的了,M晓。”


  1. 摘自 mothy 歌曲《バリーゾールの子供は一人っ子》。 ↩︎

  2. 全名为 Original Isotopy Exuviae Reconstruction。 ↩︎

  3. 详见 Evillious 系列。 ↩︎

「退群杯」3rd

Not Attended
Status
Done
Rule
ACM/ICPC
Problem
10
Start at
2022-2-12 13:30
End at
2022-2-12 18:30
Duration
5 hour(s)
Host
Partic.
205