Processing math: 100%
Array division - MarisaOJ: Marisa Online Judge

Array division

Time limit: 1000 ms
Memory limit: 256 MB
Given an array A of n integers. The cost of a subarray Al...r is (Al−Ar)2. Your task is dividing array A in k subarrays so that the total cost is minimized. ### Input - The first line contains two integers n,k. - The second line contains n integer Ai. ### Output - Print an integer is the minimum cost. ### Constraints - 1≤n≤104. - 1≤k≤min(100,n). - 1≤Ai≤109. ### Example Input: 5223154 Output: 1
Topic
Data structure
Dynamic Programming
Geometry
Rating 2000
Source CS Academy
Solution (0) Solution