P5574 [CmdOI2019] Task Assignment Problem

What does it feel like to kick off the power cable while mining?

On a computer with $k$ CPUs, there are $n$ computing tasks waiting to be executed. Let $a_i$ be the priority of the $i$-th task. For convenience, $a$ is a permutation. Now, these tasks need to be assigned to the CPUs to be processed. Due to reasons such as memory limits, one CPU can only handle one continuous segment of tasks, and it must execute them in order (from left to right). **Within a single CPU**, the disorder is defined as the number of pairs of tasks where the former is executed earlier, but the latter has a higher priority. Minimize the sum of disorders over all CPUs.

The first line contains two integers $n, k$, representing the number of tasks and the number of CPUs. The second line contains $n$ integers, representing $a_{1\sim n}$.

Output one integer, representing the minimum possible sum of disorders.

### Sample Explanation - **Sample #1** In this case, all tasks can only be assigned to a single CPU. The first task forms disorder pairs with all other tasks; the last two tasks also form a disorder pair, for a total of $5$. - **Sample #2** The first CPU processes task $1$ alone, with disorder $0$. The second CPU processes $\{5,4,2,3\}$, with disorder $1$. ### Constraints and Notes For all testdata, it is guaranteed that $1\leq n\leq 2.5\times 10^4$, $1\leq k\leq 25$, $a\leq n$. | Test Point ID | $n$ | $k$ | | :--: | :--: | :--: | | $1\sim 2$ | $2.5\times 10^4$ | $1$ | | $3$ | $2.5\times 10^4$ | $2$ | | $4\sim 5$ | $1000$ | $10$ | | $6\sim 10$ | $2.5\times 10^4$ | $25$ | Translated by ChatGPT 5