[Solution] Traps Codeforces Solution | Codeforces Problem Solution 2022

[Solution] Traps Codeforces Solution | Codeforces Problem Solution 2022

D. Traps

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

There are 𝑛$n$ traps numbered from 1$1$ to 𝑛$n$. You will go through them one by one in order. The 𝑖$i$-th trap deals 𝑎𝑖$a_i$ base damage to you.

Instead of going through a trap, you can jump it over. You can jump over no more than 𝑘$k$ traps. If you jump over a trap, it does not deal any damage to you. But there is an additional rule: if you jump over a trap, all next traps damages increase by 1$1$ (this is a bonus damage).

Note that if you jump over a trap, you don't get any damage (neither base damage nor bonus damage). Also, the bonus damage stacks so, for example, if you go through a trap 

Solution Click Below:-  CLICK HERE

𝑖$i$ with base damage 𝑎𝑖$a_i$, and you have already jumped over 3$3$ traps, you get (𝑎𝑖+3)$(a_i+3)$ damage.

You have to find the minimal damage that it is possible to get if you are allowed to jump over no more than 𝑘$k$ traps.

Digit Minimization Codeforces Solution

Z mod X = C Codeforces Solution

Column Swapping Codeforces Solution

Traps Codeforces Solution

MEX vs DIFF Codeforces Solution

Diverse Segments Codeforces Solution

Euclid Guess Codeforces Solution

Hard Cut Codeforces Solution

Input

The input consists of multiple test cases. The first line contains a single integer 𝑡$t$ (1≤𝑡≤100$1\le t\le 100$) — the number of test cases. Description of the test cases follows.

The first line of each test case contains two integers 𝑛$n$ and 𝑘$k$ (1≤𝑛≤2⋅105$1\le n\le 2\cdot {10}^5$, 1≤𝑘≤𝑛$1\le k\le n$) — the number of traps and the number of jump overs that you are allowed to make.

The second line of each test case contains 𝑛$n$ integers 𝑎1,𝑎2,…,𝑎𝑛$a_1,a_2,\dots ,a_n$ (1≤𝑎𝑖≤109$1\le a_i\le {10}^9$) — base damage values of all traps.

It is guaranteed that the sum of 𝑛$n$ over all test cases does not exceed 2⋅105$2\cdot {10}^5$.

Output

For each test case output a single integer — the minimal total damage that it is possible to get if you are allowed to jump over no more than 𝑘$k$ traps.