AT_abc247_g [ABC247G] 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$ 行依次输出恰好由 $i$ 个人组成的梦想团队的最大强度和。

输入输出样例 #1

输入 #1

3
1 1 100
1 20 10
2 1 1

输出 #1

2
100
11

输入输出样例 #2

输入 #2

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

输出 #2

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

• 由 $1$ 个人组成的梦想团队，当选择第 $1$ 名程序员时，强度和最大为 $100$。
• 由 $2$ 个人组成的梦想团队，当选择第 $2$、$3$ 名程序员时，强度和最大为 $11$。
• 无法组成恰好 $3$ 个人的梦想团队。

由 ChatGPT 4.1 翻译