2192C.md (2730B)
1 Source: https://codeforces.com/problemset/problem/2192/C 2 3 C. All-in-one Gun 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 developing a new shooter game, but since there are a lot of shooter games out there, you decide to have something unique in your game. 22 23 You have an all-in-one gun that shoots bullets in a fixed order. There are $n$ bullets in the magazine, the $i$-th of which deals $a_i$ damage. The enemy starts with $h$ health and dies when its health becomes $\le 0$. 24 25 The gun shoots one bullet per second. After firing all $n$ bullets, it must reload, which takes $k$ seconds. Reloading always restores the same sequence of bullets $[a_1, a_2, \ldots, a_n]$. You cannot reload early; you must empty the magazine first. At the start, the magazine is already full. 26 27 Before the fight begins, you may perform at most one swap: pick any indices $1 \le i \lt j \le n$ and exchange $a_i$ with $a_j$. 28 29 Your task is to find the minimum number of seconds needed to kill the enemy, taking into account this optional single swap. 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 10^4$). The description of the test cases follows. 34 35 The first line of each testcase contains three integer $n$, $h$ and $k$ ($2 \le n \le 2\cdot 10^5$, $ 1 \le h, k \le 10^9$) — the size of magazine, health of your enemy and time required to reload the magazine. 36 37 The second line of each testcase contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^9$). 38 39 It is guaranteed that the sum of $n$ does not exceed $2 \cdot 10^5$ over all test cases. 40 41 Output 42 43 For each testcase, output a single integer denoting the minimum time required to kill the enemy. 44 45 Example 46 47 Input 48 49 ``` 50 6 51 52 5 10 1 53 54 4 2 3 5 3 55 56 5 10 1 57 58 4 2 3 7 3 59 60 3 10 2 61 62 1 2 3 63 64 2 5 3 65 66 2 1 67 68 3 18 5 69 70 1 2 3 71 72 4 10 10 73 74 1 1 2 2 75 ``` 76 77 Output 78 79 ``` 80 3 81 82 2 83 84 7 85 86 6 87 88 19 89 90 17 91 ``` 92 93 Note 94 95 In the first test case, you swap the bullets present at index $2$ and $5$. This makes array $a$ as $4, 3, 3, 5, 2$. 96 97 After $3$ seconds, the health of your enemy will be $10 - 4 - 3 - 3 = 0$, hence the enemy dies in $3$ seconds. It can be shown that achieving time to kill less than $3$ is not possible. 98 99 In the third test case, you swap bullets present at index $1$ and $3$. This makes array $a$ as $3, 2, 1$. 100 101 In $7$ seconds, you shoot the entire first magazine ($3$ seconds) $+$ reload a new magazine ($2$ seconds) $+$ shoot the first and the second bullet from the new magazine ($2$ seconds). 102 103 The health of the enemy will be $10 - 3 - 2 - 1 - 3 - 2 = -1$, hence the enemy dies in $7$ seconds. It can be shown that achieving time to kill less than $7$ is not possible.