← 返回题目列表

AtCoder · abc247_g

G. 梦之队

中文机器翻译题面 查看原题

分数: 600 点

问题陈述

有 N 有竞争力的程序员。
的 i第一个竞争性程序员属于大学 A_i, 擅长科目 B_i,并且具有以下能力 C_i.

考虑一个由以下人员组成的团队 N 人。 让我们称这样的团队为 梦之队 如果满足以下两个条件:

  • 团队中的任何两个人都属于不同的大学。
  • 团队中的任意两个人擅长不同的科目。

让 k 是梦之队的最大可能成员数量。 对于每个 i=1,2,\ldots,k,解决下列问题。

问题:求梦之队成员的最大权力总和 i 人。

约束

  • 1 \leq N \leq 3\times 10^4
  • 1 \leq A_i,B_i \leq 150
  • 1 \leq C_i \leq 10^9
  • 输入中的所有值都是整数。

输入

输入由标准输入按以下格式给出:

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,按此顺序。


示例输入 1

3
1 1 100
1 20 10
2 1 1

示例输出 1

2
100
11
  • 梦之队成员的力量总和恰好由 1 人是 100,当团队由 1-st 有竞争力的程序员。
  • 梦之队成员的力量总和恰好由 2 人是 11,当团队由 2-nd 和 3-rd 有竞争力的程序员。
  • 不可能组建一支完全由以下人员组成的梦之队 3 人。

示例输入 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