P2263 Beyond Destiny

kkksc03 and lzn embarked on a treasure hunt. After their tireless efforts, they finally solved all the puzzles and crossed the great river using the art of riding the wind. The destination is now just one step away from them...

They are now at a barrier formation that connects the ancient and modern worlds. Generally, even gods cannot traverse time and space. However, lin_toto gave them a hint and revealed the secret of this formation. He told kkksc03 and lzn that as long as they work together, they can change their destiny and break the shackles of the barrier. lin_toto led them to the front of the formation. What lay before them was a huge yet damaged wall, composed of several consecutive groups of magical bricks (each magical brick is a cube of size $1\times1\times1$), and the heights of these groups are all different. From experience, only by making the heights of at least $K$ consecutive groups that form this wall equal can they break through the entrance of the formation, summon help from the divine realm, and traverse time and space. They can perform the following operations: remove one brick from the wall, or take one brick from a nearby pile of magical bricks (assume an unlimited supply) and place it on the wall. Each brick moved consumes one unit of energy from kkksc03 and lzn. lzn wants to minimize the total energy consumed. Now kkksc03 has come to you with this problem. Can you help him compute the minimum energy required?

One line with two positive integers $N, K$. Then $N$ lines follow, each representing the height $H_i$ of a group of magical bricks.

A single integer, the minimum energy required.

For $10\%$ of the testdata, $1 \le N \le 10$, $2 \le K \le N$, $0 \le H_i \le N$. For $20\%$ of the testdata, $K = 2$. For $40\%$ of the testdata, $1 \le N \le 500$, $2 \le K \le N$, $0 \le H_i \le N$. For $80\%$ of the testdata, $1 \le N \le 10^5$, $2 \le K \le N$, $0 \le H_i \le 10^6$. For $100\%$ of the testdata, $1 \le N \le 5 \times 10^5$, $2 \le K \le N$, $0 \le H_i \le 10^{12}$, and all $H_i$ are distinct. Translated by ChatGPT 5