#P10526. [2021年联测]珠宝

    ID: 9643 传统题 2000ms 888MiB 尝试: 4 已通过: 1 难度: 7 上传者: 标签>贪心数据结构CF2300排序堆模拟背包DP

[2021年联测]珠宝

珠宝(jewels)

问题描述

你有NN个珠宝,编号是 11 到NN。第ii 个珠宝有颜色CiC_{i} 和价值ViV_{i}。

你要选择一些珠宝,满足对于任意选择了的珠宝,都有至少一个其它选择了的珠宝和这个珠宝颜色相同。

对于每个1≤i≤N1\le i\le N求出,是否存在一种选择珠宝的方案满足选了恰好ii个珠宝,如果没有,输出−1-1,否则输出这些方案中最大的珠宝价值总和(不输出具体选择)。

输入格式

第一行输入两个正整数NN 和KK,表示珠宝数和颜色数。

接下来NN行每行两个正整数CiC_{i} 和ViV_{i},描述一个珠宝。

输出格式

NN 行,第ii 行输出选恰好ii个珠宝的答案。

样例 1 输入

5 2
1 1
1 2
1 3
2 4
2 5

样例 1 输出

-1
9
6
14
15

样例 2 输入

15 5
3 87
1 25
1 27
3 58
2 85
5 19
5 39
1 58
3 12
4 13
5 54
4 100
2 33
5 13
2 55

样例 2 输出

-1
145
173
285
318
398
431
491
524
576
609
634
653
666
678

数据规模与约定

对于所有数据,保证 $1 \leq N \leq2 \times10^{5} , 1 \leq K \leq\lfloor\frac{N} {2} \rfloor, 1 \leq C_{i} \leq K , 1 \leq V_{i} \leq10^{9} .$。

子任务编号 分值 其他限制
1 2020 N≤2000N\le 2000
2 10 K≤2K\le 2
33 2020 K≤10K\le 10
44 5050 无