#P17800. [Ontak2024]PLA
[Ontak2024]PLA
题目描述
有 道题,分为 个类别。题目 属于类别 ,预计解题时间为 。
一个训练方案是题目集合,需要满足:对每个类别 ,所选题数至少为 ,至多为 。
方案耗时等于所选题目的时间之和。只要选择的题目集合不同,就视为不同方案,即使总耗时相同。
把所有合法方案的耗时按非降序排列,输出前 项。不同方案的相同耗时需要重复输出;如果合法方案不足 个,剩余位置输出 。
输入格式
第一行整数 ,表示子任务编号。
第二行三个整数 。
接下来 行,第 行两个整数 。
再接下来 行,第 行两个整数 ,描述类别 的选择数量范围。
输出格式
输出恰好 行,每行一个整数。先按非降序输出存在的前 个方案耗时;不足的项输出 -1。
数据范围
- 。
- ,。
- 。
- 不保证每个类别都有题,也不保证存在合法方案。
- 空集在满足所有类别限制时也是一个方案,耗时为 。
样例 1
输入:
0
4 2 8
1 3
2 2
1 5
2 4
0 1
1 1
输出:
2
4
5
7
7
9
-1
-1
两种不同方案的耗时都为 ,因此两次输出 。
样例 2
输入:
0
3 3 4
1 1
2 2
3 3
0 1
1 2
1 1
输出:
5
6
-1
-1
子任务
| 编号 | 附加限制 | 分值 |
|---|---|---|
| 1 | ,所有 | 18 |
| 2 | ,所有 | 17 |
| 3 | 所有 | 29 |
| 4 | 所有 | 14 |
| 5 | 无附加限制 | 22 |
注意子任务 2 限制的是题目耗时 ,不是 ; 仍遵守全局上限。