A. 深界六层-黎明卿的绝界行

    传统题 1000ms 256MiB

深界六层-黎明卿的绝界行

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

题目描述

来去无回之都

“欢迎来到『绝界』,我的小朋友们。” ——黎明卿 · 祈并之手

黎明卿带着普鲁修卡的“祝福”踏上绝界行。他必须从第 1 层一路向下穿越共 n 个深渊层,最终抵达“终点之祭坛”。

每进入更深的一层,深渊的“上升负荷”会显现为一段序列的逆序对数量,对他造成伤害。 定义:某层的上升负荷 = 该层序列中的逆序对个数(即满足 i < j 且 ai > aj 的数对数量)。 注意,逆序对不止相邻的。

黎明卿拥有:

  • k 点生命值(无数次实验积累的抗性)
  • m 个祈并之囊(道具,可完全抵消某一层的上升负荷;每个只能使用一次)

黎明卿要合理选择在哪些层使用祈并之囊,使得 所有未被抵消的伤害总和 ≤ k。 请判断他是否能成功完成这次绝界行。

输入格式

第一行输入三个整数$n(1 \le n \le 100), m(0 \le m \le 10), k(1 \le k \le 10^4)$。

接下来有nn 块,每块两行:

  1. 第一行:该层序列长度len(1≤len≤100)len(1 \le len \le 100)

  2. 第二行:lenlen 个 互不相同的整数a1,a2,...,alen(1≤ai≤1000)a_1,a_2,...,a_{len}(1 \le a_i \le 1000)。

这些整数构成该层的“诅咒序列”。

输出格式

若黎明卿能安全抵达终点之祭坛,输出YESYES,否则输出NONO。

样例

3 1 8
4
1 4 3 2
3
3 1 2
2
2 1
YES

2 0 5
3
1 3 2
4
4 3 2 1
NO

2025级新生训练·附加题

未参加
状态
已结束
规则
XCPC
题目
9
开始于
2025-11-26 18:30
结束于
2025-11-26 21:30
持续时间
3 小时
主持人
参赛人数
126