409178: GYM103449 F àPaPdnarG

Memory Limit:512 MB Time Limit:3 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

F. àPaPdnarGtime limit per test3 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard output

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

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

Output

Print one integer : The minimum cost you can have.

Scoring
  • 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
ExampleInput
4 2
4 3 2 1
Output
2
Note

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

加入题单

上一题 下一题 算法标签: