No.3764 Graduation Live
タグ : / 解いたユーザー数 3
作問者 :
ei1333333
/ テスター :
kyoprouno
ei13333333
Problem Statement
A group of $3$ people, Yachiyo, Kaguya, and Iroha, will perform a live concert.
For each of the $N$ candidate songs for the concert, "which unit sings it" is specified in advance.
The $i (1 \leq i \leq N)$-th song is one of the following $6$ types.
- $t_i = 1$: Solo song (Yachiyo). Consumes $1$ of Yachiyo's stamina.
- $t_i = 2$: Solo song (Kaguya). Consumes $1$ of Kaguya's stamina.
- $t_i = 3$: Solo song (Iroha). Consumes $1$ of Iroha's stamina.
- $t_i = 4$: Duet song (Yachiyo & Kaguya). Consumes $1$ of stamina from each of Yachiyo and Kaguya.
- $t_i = 5$: Duet song (Yachiyo & Iroha). Consumes $1$ of stamina from each of Yachiyo and Iroha.
- $t_i = 6$: Duet song (Kaguya & Iroha). Consumes $1$ of stamina from each of Kaguya and Iroha.
Also, if the $i$-th song is selected, the audience gains satisfaction $v_i$.
The stamina of Yachiyo, Kaguya, and Iroha is $Y, K, I$, respectively.
You cannot select the same song $2$ or more times, and you cannot make a selection in which the total stamina consumed by any person exceeds $Y, K, I$, respectively.
Let $C$ be the maximum number of songs that can be selected while satisfying these conditions.
For each integer $c\ (1 \leq c \leq C)$, find the maximum total audience satisfaction $X_c$ when selecting a total of $c$ songs.
You are given $T$ test cases; solve each of them.
Constraints
- $1 \leq T \leq 10^5$
- $1 \leq N \leq 3 \times 10^5$
- $0 \leq Y, K, I \leq N$
- $1 \leq t_i \leq 6$
- $|v_i| \leq 10^9$
- The sum of $N$ over all test cases is at most $3 \times 10^5$
- All input values are integers
Input
$T$
$\mathrm{case}_1$
$\mathrm{case}_2$
$:$
$\mathrm{case}_T$
Here, $\mathrm{case}_i$ is the $i$-th test case, given in the following format.
$N$ $Y$ $K$ $I$ $t_1$ $v_1$ $t_2$ $v_2$ $:$ $t_N$ $v_N$
Output
Print $T$ lines. On the $i$-th line, print the answer to $\mathrm{case}_i$ in the following format.
$C$ $X_1$ $X_2$ $\cdots$ $X_C$
If $C=0$, print only $0$.
Sample
Sample 1
Input
1 6 1 1 1 1 5 2 4 3 3 4 10 5 9 6 8
Output
3 10 13 12
At most $C = 3$ songs can be selected.
When selecting $1$ song, selecting song $4$ gives a total satisfaction of $10$, which is the maximum.
When selecting $2$ songs, selecting songs $3, 4$ gives a total satisfaction of $3+10=13$, which is the maximum.
When selecting $3$ songs, selecting songs $1, 2, 3$ gives a total satisfaction of $5+4+3=12$, which is the maximum.
Sample 2
Input
2 5 2 1 1 1 8 1 8 4 10 5 10 6 9 6 0 2 2 1 100 2 -2 2 -3 3 -4 3 -5 5 -1
Output
3 10 20 25 4 -2 -5 -9 -14
The total satisfaction may be negative.
Sample 3
Input
2 3 3 3 0 3 1 5 2 6 3 3 1 1 1 4 0 5 0 6 0
Output
0 1 0
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。