codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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$.