409178: GYM103449 F àPaPdnarG

GrandPaPà gives you an array $$$A$$$ of $$$N$$$ elements. Your task is to split this array into $$$K$$$ non-intersecting non-empty contiguous subarrays such that the sum of all subarrays costs is minimum. The cost of an array $$$V$$$ is the number of pairs of indices $$$(i,j)$$$ such that i<j and $$$V_i>V_j.$$$

Input consists of numbers $$$N,K$$$ and an array $$$A$$$ of $$$N$$$ elements.

Print one integer : The minimum cost you can have.

• For all test data $$$N \cdot K \le 10^6$$$ , $$$1\le K \le N , -10^9 \le A_i \le 10^9$$$
• For 5 points $$$K = 1$$$.
• For another 10 points $$$K = 2$$$.
• For another 20 points $$$N,K \le 100$$$
• For the remaining test data , there are no further restrictions

4 2
4 3 2 1

2

The optimal split is [4,3][2,1]. The cost of this split is $$$1+1=2$$$ , which is minimum possible.