← 返回题目列表

Codeforces · 1787/C

C. 拆下支架

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

RSJ 有一个由 $$$n$$$ 整数 $$$a_1,a_2, \ldots, a_n$$$ 和一个整数 $$$s$$$ 组成的序列 $$$a$$$。对于每个 $$$a_2,a_3, \ldots, a_{n-1}$$$,他选择了一对非负整数 $$$x_i$$$ 和 $$$y_i$$$,使得 $$$x_i+y_i=a_i$$$ 和 $$$(x_i-s) \cdot (y_i-s) \geq 0$$$。

现在他对值 $$$$$$F = a_1 \cdot x_2+y_2 \cdot x_3+y_3 \cdot x_4 + \ldots + y_{n - 2} \cdot x_{n-1}+y_{n-1} \cdot a_n.$$$$$$ 感兴趣

请帮他找到通过最优选择$$$x_i$$$和$$$y_i$$$可以获得的最小可能值$$$F$$$。可以证明,总是至少有一种有效的方法来选择它们。

输入

每个测试包含多个测试用例。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。

每个测试用例的第一行包含两个整数 $$$n$$$、$$$s$$$ ($$$3 \le n \le 2 \cdot 10^5$$$; $$$0 \le s \le 2 \cdot 10^5$$$)。

第二行包含 $$$n$$$ 整数 $$$a_1,a_2,\ldots,a_n$$$ ($$$0 \le a_i \le 2 \cdot 10^5$$$)。

保证$$$n$$$之和不超过$$$2 \cdot 10^5$$$。

输出

对于每个测试用例,打印 $$$F$$$ 的最小可能值。

示例

输入 #1

10
5 0
2 0 1 3 4
5 1
5 3 4 3 5
7 2
7 6 5 4 3 2 1
5 1
1 2 3 4 5
5 2
1 2 3 4 5
4 0
0 1 1 1
5 5
4 3 5 6 4
4 1
0 2 1 0
3 99999
200000 200000 200000
6 8139
7976 129785 12984 78561 173685 15480

输出 #1

0
18
32
11
14
0
16
0
40000000000
2700826806

注意

在第一个测试用例中,$$$2\cdot 0+0\cdot 1+0\cdot 3+0\cdot 4 = 0$$$。

在第二个测试用例中,$$$5\cdot 1+2\cdot 2+2\cdot 2+1\cdot 5 = 18$$$。