← 返回题目列表

Codeforces · 2207/C

C. 我的水呢?

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

3 级 — 大卫·路易斯·奥尔特加,我的水在哪里?

令 $$$n, h$$$ 为正整数。沼泽鳄鱼的浴缸需要水,你的任务是把水送给他。在他的房子上方,有一个 $$$h \times n$$$ 的泥土和水瓷砖网格,其中 $$$n$$$ 列编号为 $$$1、\ldots、n$$$。在 $$$i$$$ 列中,底部的 $$$a_i$$$ 瓷砖是泥土,顶部的其余部分是水瓷砖。

要向沼泽供水,您可以在任何非污垢瓷砖上放置排水管。放置排水沟会通过仅在网格上向下、向左或向右移动而不穿过任何污垢瓷砖来消除所有可以进入排水沟的水瓷砖。

例如,将排水管放置在下面网格中的 $$$\times$$$ 上将会排水左上角和右上角的水格,并导致 $$$10$$$ 格被排水:

放置后你最多可以获得多少水到沼泽 最多两个 排水沟?请注意,可能被任一排水管带走的水块仅计算一次。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^3$$$)。测试用例的描述如下。

第一行包含两个整数 $$$n$$$ 和 $$$h$$$ ($$$1 \leq n \leq 2000, 1 \leq h \leq 10^9$$$) — 网格的列数和高度。

下一行包含 $$$n$$$ 整数 $$$a_i$$$ ($$$1 \leq a_i \leq h$$$) — $$$i$$$ 列中泥土的高程。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2000$$$。

输出

对于每个测试用例,输出一个整数——可以使用以下方法获得的水瓷砖的最大数量 最多两个 排水沟。

示例

输入
复制

6
7 4
1 3 1 2 3 1 1
8 10
7 5 1 3 2 5 6 8
1 1
1
10 20
5 2 1 2 1 3 6 7 1 1
5 1000000000
1 420420420 1 420420420 1
1 1000000000
1

输出
复制

14
43
0
170
3738738738
999999999

注意

在第一个测试用例中,网格是语句中显示的示例。如图所示放置排水管,可以排出 $$$14$$$ 格的水:

在第二个测试用例中,网格如下所示:

可以通过如下所示放置排水沟来排出所有 $$$43$$$ 方块的水:

在第三个测试用例中,网格是单个污垢瓷砖,并且不能放置排水沟。所以,答案是$$$0$$$。