2234C.md (3071B)
1 Source: https://codeforces.com/problemset/problem/2234/C 2 3 C. Vessels, Heights and Two Versions (Easy Version) 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 This is the easy version of the problem. The difference between the versions is that in this version, constraints on $n$ and on the number of test cases are smaller. You can hack only if you solved all versions of this problem. 22 23 There are $n$ communicating vessels of infinite height arranged in a circle. The base area of each vessel is $1$ cm$^2$, and between the $i$-th vessel and the $(i \bmod n) + 1$-th vessel there is a connection of negligible volume at height $h_i$ cm. For each vessel $i$, find the maximum total volume of water in cm$^3$ that can be placed in these vessels under the condition that the $i$-th vessel remains empty. 24 25 Formally, you are given an array $h_1, h_2, \ldots, h_n$. A cyclic array of non-negative integers $w_1, w_2, \ldots, w_n$ is called good if the following holds: 26 27 * For every $i$ from $1$ to $n$, if $\max(w_i, w_{i \bmod n + 1}) \gt h_i$, then $w_i = w_{i \bmod n + 1}$. In other words, if the maximum of two neighboring elements of the array $w$ exceeds the corresponding element of the array $h$, then these two neighboring elements of the array $w$ must be equal. 28 29 For each $i$ from $1$ to $n$, output the maximum possible sum $w_1 + w_2 + \ldots + w_n$ among all good arrays $w_1, w_2, \ldots, w_n$, under the condition that $w_i = 0$. 30 31 Input 32 33 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 1000$). The description of the test cases follows. 34 35 The first line of each test case contains one integer $n$ ($3 \le n \le 3000$) — the number of vessels. 36 37 The second line of each test case contains $n$ integers $h_1, h_2, \ldots, h_n$ ($1 \le h_i \le 10^9$) — the heights of the partitions between the vessels. 38 39 It is guaranteed that the sum of $n$ over all test cases does not exceed $3000$. 40 41 Output 42 43 For each test case, output $n$ integers — the $l$-th integer means the maximum total volume of water in cm$^3$ in the vessels under the condition that the $l$-th vessel remains empty. 44 45 Example 46 47 Input 48 49 ``` 50 4 51 52 4 53 54 1 2 3 4 55 56 5 57 58 5 3 1 5 2 59 60 6 61 62 3 4 2 6 1 5 63 64 7 65 66 1 2 1 4 2 3 5 67 ``` 68 69 Output 70 71 ``` 72 6 6 7 9 73 74 17 16 14 14 17 75 76 21 21 20 20 21 21 77 78 17 17 17 17 21 21 22 79 ``` 80 81 Note 82 83 Consider the first test case. 84 85 * To keep vessel $1$ empty, one good array is $w = [0, 1, 2, 3]$, with a total of $6$ cm$^3$ of water. 86 * To keep vessel $2$ empty, one good array is $w = [1, 0, 2, 3]$, with a total of $6$ cm$^3$ of water. 87 * To keep vessel $3$ empty, one good array is $w = [2, 2, 0, 3]$, with a total of $7$ cm$^3$ of water. 88 * To keep vessel $4$ empty, one good array is $w = [3, 3, 3, 0]$, with a total of $9$ cm$^3$ of water. 89 90 For example, the array $w = [2, 2, 0, 4]$ is not good, because $\max(w_3, w_4) \gt h_3$, and therefore $w_3 = w_4$ must hold. 91 92 It can be shown that each of the arrays above has the maximum possible sum among all suitable options.