CCO Preparation Test 3 P2 - Packing Up

View as PDF

Submit solution

Points: 25 (partial)
Time limit: 1.0s
Memory limit: 128M

Problem type

Bruce is going to Waterloo to watch CCO. He needs to pack up all of his books. There are N books, which are numbered from 1 to N. Bruce has a super compressor, which will compress the book i into one dimension with length C_i. After compressing, Bruce will put his books into a number of one dimensional containers. Since Bruce doesn't want to mess up the order of his books, he has to pack up books in the order from 1 to N. Bruce can pack one book into one container or multiple books into one container. If multiple books are placed into one container, Bruce will insert a separator with unit length between any two consecutive books. Bruce wants all separators to separate two books from each other, and there should only be one separator between two adjacent books. Thus, the length of the container for holding book i to book j will be x=j-i+\sum_{k=i}^j C_k. The cost of a container is calculated by (x-L)^2, where x is the container's length and L is a given constant. Bruce can buy containers with arbitrary lengths from the supermarket. But Bruce wants to pay the minimal cost. Could you please help Bruce to find the minimal cost of containers to pack up all his books?

Input Specification

The first line of input will consist two integers, N (1 \le N \le 2 \times 10^6) and L (1 \le L \le 10^7).
Each of the following N lines will consist of one integer C_i, the length of book i (1 \le C_i \le 10^7).

Note: additional data worth 20% of the points have been added to break unintended solutions. Data provided courtesy of ChrisT.

Output Specification

Output one integer, the minimal cost Bruce needs to pay for all the containers. It is guaranteed that Bruce will not pay more than 2^{63}-1 in total.

Sample Input

5 4

Sample Output


Explanation of Output for Sample Input

Bruce can pack book 1 into container 1 with a cost of (3-4)^2=1, book 2 into container 2 with a cost of (4-4)^2=0, book 3 and book 4 into container 3 with a cost of (2+1+1-4)^2=0 (since there is a separator between book 3 and book 4), and finally book 5 into container 4 with a cost of (4-4)^2=0. The total cost is 1.


  • 41
    kadbury  commented on June 8, 2015, 10:37 p.m.

    i told my mom i already solved this problem, please help

    • 27
      bruce  commented on June 9, 2015, 12:28 a.m.

      You need to use 1D/1D dynamic programming to optimize the time complexity to O(n) or O(nlogn). Please check this link.