P9505 "MGOI" Simple Round I | D. Magic Ring

> The best weapon is not always the most suitable one; only the most suitable weapon is the best. — Hall Magician W

Little M is facing the task of awakening their soul artifact, the magic ring. There are $n$ nodes on the magic ring. Each node has a magic sprite, and each magic sprite has a fixed **magic supply value**. These magic supply values form a permutation of $0 \sim n-1$. Little M may choose to activate or not activate a magic sprite. However, to awaken the magic ring, they must activate **at least** $k(\ge 2)$ magic sprites. Each magic sprite produces an **enchantment value** regardless of whether it is activated: - For an activated magic sprite, the enchantment value it produces is the **square** of its magic supply value. - For a non-activated magic sprite, it looks left and right along the ring, respectively toward the nearest activated magic sprite on each side. It chooses the one with the larger magic supply value as the "target sprite", and the enchantment value it produces equals the product of the magic supply value of this "target sprite" and the **distance that the line of sight passes through when looking at this "target sprite"**. As a beginner, Little M wants, under the condition of activating the magic ring, to minimize the sum of the enchantment values of all magic sprites, so as to better control the energy of the magic ring.

The first line contains two integers $n, k$. The second line contains $n$ integers, representing the magic supply value of the magic sprite on each node.

Output one integer in one line, representing the minimum possible sum of enchantment values.

**[Sample 1 Explanation]** Activate the magic sprites with magic supply values $0$ and $1$. - The magic sprite with magic supply value $3$ chooses the magic sprite with magic supply value $1$, producing an enchantment value of $1 \times 3 = 3$. - The magic sprite with magic supply value $0$ is activated, producing an enchantment value of $0^2=0$. - The magic sprite with magic supply value $1$ is activated, producing an enchantment value of $1^2=1$. - The magic sprite with magic supply value $4$ chooses the magic sprite with magic supply value $1$, producing an enchantment value of $1 \times 1 = 1$. - The magic sprite with magic supply value $2$ chooses the magic sprite with magic supply value $1$, producing an enchantment value of $1 \times 2 = 2$. The total enchantment value produced is $7$. **[Constraints]** **This problem uses bundled Subtask testdata.** For all testdata, $2\le k \le n \le 3000$, $k \le 100$. The magic supply values on each node form a permutation of $0\sim n-1$. | Subtask | $n$ | $k\le$ | Score | | :------------: | :----------: | :----------:|:----------------:| | $1$ | $10$ | $10$ | $13$ | | $2$ | $100$ | $100$ | $17$ | | $3$ | $300$ | $100$ | $21$ | | $4$ | $1000$ | $100$ | $23$ | | $5$ | $3000$ | $100$ | $26$ | Translated by ChatGPT 5