【集训队互测2021】小 C 的比赛 - 题目

在一个神秘的 OJ 上，小 C 曾经参加过 $n$ 场比赛，其中第 $i (i = 1, 2, \dots, n)$ 场比赛获得了 $a_{i}$ 积分；积分可能是正的，可能是负的，但它一定是一个 $[- 2, 2]$ 中的整数。

由于一些原因，小 C 会挑出一个区间的比赛 $[l, r]$ ，并和大家说：“要是我只打这个区间的比赛，那么我就有 $\sum_{i = l}^{r} a_{i}$ 分了！”当然，小 C 会挑选出至少一场比赛，而且选出区间的比赛积分总和是所有区间里最大的，而这个积分总和则是他对自己发挥的满意程度。

随着时间的流逝，小 C 逐渐忘记了自己每场比赛的分数，也忘了他对这些比赛的满意程度，他只记得每种分数的比赛打了多少场，而小 C 想知道，他满意程度最小可能是多少。于是他来请求于你。

本题有多组测试数据。

第一行一个正整数 $T$ ，表示数据组数。

下面 $T$ 行，每行 $c_{- 2}, c_{- 1}, c_{0}, c_{1}, c_{2}$ 五个非负整数，分别表示每种分数的比赛场数。你可以自行算出 $n = c_{- 2} + c_{- 1} + c_{0} + c_{1} + c_{2}$ 。

每组测试数据输出两行。第一行一个整数，表示小 C 满意程度的可能最小值。

第二行 $n$ 个整数 $a_{1}, a_{2}, \dots, a_{n}$ ，表示达到此最小值的任意一种可能的比赛得分情况。

1
1 1 0 2 2

3
1 -1 2 -2 1 2

令 $\sum n$ 表示一组数据中 $n$ 的总和。对所有数据，保证 $1 \leq T \leq 10000, 1 \leq n, \sum n \leq 5 \times 10^{5}$ 。

子任务编号	$n \leq$	特殊性质	分值
$1$	$20$	$T \leq 5$	$18$
$2$	$40$	$T \leq 5$	$18$
$3$	$5 \times 10^{5}$	$c_{- 2} = 0$	$18$
$4$	$5 \times 10^{5}$	$c_{2} = 0$	$18$
$5$	$5 \times 10^{5}$	无	$28$

时间限制： $1 s$

空间限制： $512 MB$

Universal Online Judge