Dream Team

题目描述

有 $N$ 名竞赛选手。
第 $i$ 名竞赛选手属于大学 $A_i$，擅长学科 $B_i$，并且具有实力 $C_i$。 考虑由这 $N$ 人中的若干人组成的队伍。如果满足以下两个条件，则称这样的队伍为理想队：

队中任意两个人来自不同的大学。 队中任意两个人擅长不同的学科。

令 $k$ 为理想队可能的最大成员数。对于每个 $i=1,2,\ldots,k$，解决以下问题。 问题：求一个由恰好 $i$ 人组成的理想队中选手实力和的最大值。

输入格式

输入由标准输入给出，格式如下： $N$ $A_1$ $B_1$ $C_1$ $A_2$ $B_2$ $C_2$ $\vdots$ $A_N$ $B_N$ $C_N$

输出格式

令 $k$ 为理想队可能的最大成员数。
第一行输出 $k$。然后输出接下来的 $k$ 行，每行包含对于 $i=1,2,\ldots,k$ 的问题的答案，按此顺序输出。

3
1 1 100
1 20 10
2 1 1

2
100
11

10
1 4 142135623
2 6 457513110
3 1 622776601
5 1 961524227
2 2 360679774
2 4 494897427
3 7 416573867
5 2 915026221
1 7 320508075
5 3 851648071

4
961524227
1537802822
2032700249
2353208324

提示

$1 \leq N \leq 3\times 10^4$ $1 \leq A_i,B_i \leq 150$ $1 \leq C_i \leq 10^9$ 输入中的所有数值均为整数。由恰好 $1$ 人组成的理想队的成员实力和为 $100$，当队伍由第 $1$ 位竞赛选手组成时。 由恰好 $2$ 人组成的理想队的成员实力和为 $11$，当队伍由第 $2$ 位和第 $3$ 位竞赛选手组成时。 不可能组成恰好 $3$ 人的理想队。

标签: AtCoder|abc247G

来源

AtCoder|abc247G