G - Dream Team

Contest Duration: 2022-04-10(Sun) 12:00 - 2022-04-10(Sun) 13:40 (local time) (100 minutes) Back to Home

G - Dream Team Editorial

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : $600$ 点

問題文

$N$ 人の競技プログラマがいます。
$i$ 人目の競技プログラマは、所属大学が $A_i$ 、得意分野が $B_i$ 、強さが $C_i$ です。

$N$ 人のうちの何人かによって構成されるチームであって、次の条件をともに満たすものをドリームチームと呼びます。

チームに属するどの $2$ 人の所属大学も異なる
チームに属するどの $2$ 人の得意分野も異なる

構成可能なドリームチームの人数の最大値を $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$ とする。
1行目には $k$ を出力し、その後、 $k$ 行にわたって、 $i=1,2,\ldots,k$ のときの問題に対する答えを順に出力せよ。

入力例 1Copy

Copy

出力例 1Copy

Copy

2
100
11

ちょうど $1$ 人で構成されるドリームチームは、 $1$ 人目の競技プログラマからなるとき強さの合計が $100$ で最大になります。
ちょうど $2$ 人で構成されるドリームチームは、 $2,3$ 人目の競技プログラマからなるとき強さの合計が $11$ で最大になります。
ちょうど $3$ 人で構成されるドリームチームを作ることはできません。

入力例 2Copy

Copy

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

出力例 2Copy

Copy

Score : $600$ points

Problem Statement

There are $N$ competitive programmers.
The $i$ -th competitive programmer belongs to University $A_i$ , is good at Subject $B_i$ , and has a power of $C_i$ .

Consider a team consisting of some of the $N$ people. Let us call such a team a dream team if both of the following conditions are satisfied:

Any two people belonging to the team belong to different universities.
Any two people belonging to the team are good at different subjects.

Let $k$ be the maximum possible number of members of a dream team. For each $i=1,2,\ldots,k$ , solve the following question.

Question: find the maximum sum of power of people belonging to a dream team consisting of $i$ people.

Constraints

$1 \leq N \leq 3\times 10^4$
$1 \leq A_i,B_i \leq 150$
$1 \leq C_i \leq 10^9$
All values in input are integers.

Input

Input is given from Standard Input in the following format:

 $N$ 
 $A_1$   $B_1$   $C_1$ 
 $A_2$   $B_2$   $C_2$ 
 $\vdots$ 
 $A_N$   $B_N$   $C_N$

Output

Let $k$ be the maximum possible number of members of a dream team.
Print $k$ in the first line. Then, print $k$ more lines, each containing the answer to the question for $i=1,2,\ldots,k$ , in this order.

Sample Input 1Copy

Copy

Sample Output 1Copy

Copy

2
100
11

The sum of power of members of a dream team consisting of exactly $1$ person is $100$ , when the team consists of the $1$ -st competitive programmer.
The sum of power of members of a dream team consisting of exactly $2$ people is $11$ , when the team consists of the $2$ -nd and the $3$ -rd competitive programmers.
It is impossible to form a dream team consisting of exactly $3$ people.

Sample Input 2Copy

Copy

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

Sample Output 2Copy

Copy