2207C.md (2543B)
1 Source: https://codeforces.com/problemset/problem/2207/C 2 3 C. Where's My Water? 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 | | 22 | --- | 23 | [Level 3 — David Luis Ortega, Where's My Water?](https://www.youtube.com/watch?v=3yV8PPnShSw) | 24 25 Let $n, h$ be positive integers. Swampy the Alligator needs water for his bathtub, and you are tasked with getting it to him. Above his house, there is an $h \times n$ grid of dirt and water tiles with $n$ columns numbered $1, \ldots, n$. In column $i$, the bottom $a_i$ tiles are dirt, and the rest on top are water tiles. 26 27 To get water to Swampy, you can place a drain on any tile that isn't a dirt tile. Placing a drain takes away all water tiles that can access the drain by moving only down, left, or right on the grid without crossing any dirt tiles. 28 29 For example, placing the drain on the $\times$ in the grid below will drain both the top left and top right water tiles and result in $10$ tiles being drained: 30 31 | | 32 | --- | 33 | | 34 35 What is the maximum amount of water you can get to Swampy after placing at most two drains? Note that water tiles that could have been taken by either drain are only counted once. 36 37 Input 38 39 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^3$). The description of the test cases follows. 40 41 The first line contains two integers $n$ and $h$ ($1 \leq n \leq 2000, 1 \leq h \leq 10^9$) — the number of columns and height of the grid. 42 43 The next line contains $n$ integers $a_i$ ($1 \leq a_i \leq h$) — the elevation of the dirt in column $i$. 44 45 It is guaranteed that the sum of $n$ over all test cases does not exceed $2000$. 46 47 Output 48 49 For each test case, output a single integer — the maximum number of water tiles that can be obtained with at most two drains. 50 51 Example 52 53 Input 54 55 ``` 56 6 57 58 7 4 59 60 1 3 1 2 3 1 1 61 62 8 10 63 64 7 5 1 3 2 5 6 8 65 66 1 1 67 68 1 69 70 10 20 71 72 5 2 1 2 1 3 6 7 1 1 73 74 5 1000000000 75 76 1 420420420 1 420420420 1 77 78 1 1000000000 79 80 1 81 ``` 82 83 Output 84 85 ``` 86 14 87 88 43 89 90 0 91 92 170 93 94 3738738738 95 96 999999999 97 ``` 98 99 Note 100 101 In the first test case, the grid is the example shown in the statement. It is possible to drain $14$ tiles of water by placing the drains as shown: 102 103 | | 104 | --- | 105 | | 106 107 In the second test case, the grid is shown below: 108 109 | | 110 | --- | 111 | | 112 113 It is possible to drain all $43$ tiles of water by placing the drains as shown: 114 115 | | 116 | --- | 117 | | 118 119 In the third test case, the grid is a single dirt tile, and no drains may be placed. So, the answer is $0$.