UOJ Logo Universal Online Judge

UOJ

#649. 【美团杯2021】M. 游泳

附件下载 统计

作为一名老程序员,蒜斜深受颈椎病的困扰。今天,在医生的建议下,蒜斜决定去游泳馆游泳。

蒜斜发现,游泳池被一些泳道线划分成了若干个泳道。每一条泳道线都由一些不同颜色的浮标的组成:这些浮标形成了一些长度类似的颜色段,看上去十分美观。

泳道

然而,当蒜斜仔细清点了每一种颜色的浮标数量之后,蒜斜发现尽管这些颜色段看上去长度一样,但是它们实际上使用的浮标数量是略有差异的。

蒜斜对这种现象很感兴趣,于是他进行了更多的探索。他发现只要相邻两个颜色段使用的浮标数量的差别在 $K$ 以内,那么从视觉上来说,这两段颜色看上去的长度就是差不多的。

经过测量,蒜斜发现每一条泳道的浮标数量总数永远都是 $n$ 且颜色段数量永远都是 $m$。蒜斜想要计算在 (1) 浮标数量和颜色段数量保持不变,且(2) 任何相邻两段颜色段的长度从视觉上相同 的情况下,所有颜色段长度的方差最大值是多少。

简化题面:已知一个正整数数组 $A$ 的长度是 $m$ ,里面所有数字的和是 $n$ 且任何两个相邻数字差的绝对值不超过 $K$,你需要计算 $A$ 中所有数字的方差最大值是多少。

输入格式

输入第一行包含一个整数 $t (1 \leq t \leq 10^4)$,表示数据组数。

对于每组数据,输入一行三个整数 $n,m,K(1 \leq n \leq 10^{8}, 1 \leq m \leq 100, 0 \leq K \leq 10^8)$,分别表示浮标的总数,颜色段的数量以及相邻两端浮标数量差的上限。

输出格式

对于每一组数据,输出一行一个整数,表示方差的最大值乘以 $m^2$(可以证明这个数值一定是一个整数)。如果不存在满足条件的方案,则需要输出 $-1$。

样例一

input

4
4 2 1
4 2 2
100000000 100 1
1919810 11 4514

output

0
4
8085000
24654303406

input

在第一组数据中,最优解是将两段的长度都设置为 $2$,这个时候方差为 $0$。

在第二组数据中,最优解是将两端的长度分别设置为 $1$ 和 $3$,这个时候方差为 $((2-1)^2+(2-3)^2)/2 = 1$。

限制与约定

Small Task: $K = 1$。

Large Task: 无特殊限制。

时间限制:$2\texttt{s}$

空间限制:$512\texttt{MB}$

下载

样例数据下载