1856C.md (1985B)
1 Source: https://codeforces.com/problemset/problem/1856/C 2 3 C. To Become Max 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 You are given an array of integers $a$ of length $n$. 22 23 In one operation you: 24 25 * Choose an index $i$ such that $1 \le i \le n - 1$ and $a_i \le a_{i + 1}$. 26 * Increase $a_i$ by $1$. 27 28 Find the maximum possible value of $\max(a_1, a_2, \ldots a_n)$ that you can get after performing this operation at most $k$ times. 29 30 Input 31 32 Each test contains multiple test cases. The first line of input contains a single integer $t$ ($1 \le t \le 100$) — the number of test cases. The description of the test cases follows. 33 34 The first line of each test case contains two integers $n$ and $k$ ($2 \le n \le 1000$, $1 \le k \le 10^{8}$) — the length of the array $a$ and the maximum number of operations that can be performed. 35 36 The second line of each test case contains $n$ integers $a_1,a_2,\ldots,a_n$ ($1 \le a_i \le 10^{8}$) — the elements of the array $a$. 37 38 It is guaranteed that the sum of $n$ over all test cases does not exceed $1000$. 39 40 Output 41 42 For each test case output a single integer — the maximum possible maximum of the array after performing at most $k$ operations. 43 44 Example 45 46 Input 47 48 ``` 49 6 50 51 3 4 52 53 1 3 3 54 55 5 6 56 57 1 3 4 5 1 58 59 4 13 60 61 1 1 3 179 62 63 5 3 64 65 4 3 2 2 2 66 67 5 6 68 69 6 5 4 1 5 70 71 2 17 72 73 3 5 74 ``` 75 76 Output 77 78 ``` 79 4 80 7 81 179 82 5 83 7 84 6 85 ``` 86 87 Note 88 89 In the first test case, one possible optimal sequence of operations is: $[\color{red}{1}, 3, 3] \rightarrow [2, \color{red}{3}, 3] \rightarrow [\color{red}{2}, 4, 3] \rightarrow [\color{red}{3}, 4, 3] \rightarrow [4, 4, 3]$. 90 91 In the second test case, one possible optimal sequence of operations is: $[1, \color{red}{3}, 4, 5, 1] \rightarrow [1, \color{red}{4}, 4, 5, 1] \rightarrow [1, 5, \color{red}{4}, 5, 1] \rightarrow [1, 5, \color{red}{5}, 5, 1] \rightarrow [1, \color{red}{5}, 6, 5, 1] \rightarrow [1, \color{red}{6}, 6, 5, 1] \rightarrow [1, 7, 6, 5, 1]$.