#P17800. [Ontak2024]PLA

[Ontak2024]PLA

题目描述

有 nn 道题,分为 mm 个类别。题目 ii 属于类别 cic_i,预计解题时间为 tit_i。

一个训练方案是题目集合,需要满足:对每个类别 jj,所选题数至少为 xjx_j,至多为 yjy_j。

方案耗时等于所选题目的时间之和。只要选择的题目集合不同,就视为不同方案,即使总耗时相同。

把所有合法方案的耗时按非降序排列,输出前 kk 项。不同方案的相同耗时需要重复输出;如果合法方案不足 kk 个,剩余位置输出 −1-1。

输入格式

第一行整数 s∈{0,…,5}s\in\{0,\ldots,5\},表示子任务编号。

第二行三个整数 n,m,kn,m,k。

接下来 nn 行,第 ii 行两个整数 ci,tic_i,t_i。

再接下来 mm 行,第 jj 行两个整数 xj,yjx_j,y_j,描述类别 jj 的选择数量范围。

输出格式

输出恰好 kk 行,每行一个整数。先按非降序输出存在的前 kk 个方案耗时;不足的项输出 -1。

数据范围

  • 1≤n,m,k≤2×1051\le n,m,k\le2\times10^5。
  • 1≤ci≤m1\le c_i\le m,1≤ti≤1091\le t_i\le10^9。
  • 0≤xj≤yj≤n0\le x_j\le y_j\le n。
  • 不保证每个类别都有题,也不保证存在合法方案。
  • 空集在满足所有类别限制时也是一个方案,耗时为 00。

样例 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

两种不同方案的耗时都为 77,因此两次输出 77。

样例 2

输入:

0
3 3 4
1 1
2 2
3 3
0 1
1 2
1 1

输出:

5
6
-1
-1

子任务

编号 附加限制 分值
1 n,m,k≤4000n,m,k\le4000,所有 xj=yj=1x_j=y_j=1 18
2 n,m,ti≤4000n,m,t_i\le4000,所有 xj=yj=1x_j=y_j=1 17
3 所有 xj=yj=1x_j=y_j=1 29
4 所有 xj=0x_j=0 14
5 无附加限制 22

注意子任务 2 限制的是题目耗时 tit_i,不是 kk;kk 仍遵守全局上限。