CF2245B Delete and Concatenate

给定一个长度为 $n$ 的整数数组 $a$。你的初始得分为 $0$。 你可以对数组执行以下两种操作，任意次数，直到数组变为空为止： - 选择单个元素。将该元素的值加到你的得分上，并从数组中移除该元素。 - 选择两个相邻的元素。将它们中较大的值加到你的得分上，并同时从数组中移除这两个元素。（该操作要求数组至少有 $2$ 个元素。） 每次操作后，剩下的元素会按照原有顺序拼接在一起。 给定一个整数 $c$，表示执行任意一种操作的花费。每进行一次操作（无论哪种类型），你的得分都会被减去 $c$。 请你计算你能获得的最大最终得分。

每组测试包含多个测试用例。第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例数量。对于每组测试数据： 每个测试用例的第一行包含两个整数 $n$ 和 $c$（$1 \le n \le 2 \cdot 10^5$，$0 \le c \le 10^9$），表示数组 $a$ 的长度和每次操作的花费。 第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$-10^9 \le a_i \le 10^9$），表示数组 $a$ 的元素。 保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

对于每个测试用例，输出一个整数，表示你所能获得的最大得分。

在第一个测试用例中，你只能进行一次第一种操作，得分为 $a_1-c=-1-0=-1$。 在第二个测试用例中，一种最优操作顺序如下： - 选择 $3$。得分变为 $0+3-0=3$，数组变为 $[1,1]$。 - 选择第一个 $1$。得分变为 $3+1-0=4$，数组变为 $[1]$。 - 选择 $1$。得分变为 $4+1-0=5$，数组变为空。 在第三个测试用例中，一种最优操作顺序如下： - 选择 $3$ 和第二个 $1$。得分变为 $0+\max(3,1)-2=1$，数组变为 $[1]$。 - 选择 $1$。得分变为 $1+1-2=0$，数组变为空。 由 ChatGPT 5 翻译