CCO Preparation Test 3 P2 - Packing Up - Olympiads Online Judge

CCO Preparation Test 3 P2 - Packing Up

View as PDF

Submit solution

All submissions

Best submissions

Points: 25 (partial)

Time limit: 1.0s

Memory limit: 128M

Author:

bruce

Problem type

Bruce is going to Waterloo to watch CCO. He needs to pack up all of his books. There are $N$ ~N~ books, which are numbered from $1$ ~1~ to $N$ ~N~. Bruce has a super compressor, which will compress the book $i$ ~i~ into one dimension with length $C_i$ ~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$ ~1~ to $N$ ~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$ ~i~ to book $j$ ~j~ will be $x=j-i+\sum_{k=i}^j C_k$ ~x=j-i+\sum_{k=i}^j C_k~. The cost of a container is calculated by $(x-L)^2$ ~(x-L)^2~, where $x$ ~x~ is the container's length and $L$ ~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$ ~N~ $(1 \le N \le 2 \times 10^6)$ ~(1 \le N \le 2 \times 10^6)~ and $L$ ~L~ $(1 \le L \le 10^7)$ ~(1 \le L \le 10^7)~.
Each of the following $N$ ~N~ lines will consist of one integer $C_i$ ~C_i~, the length of book $i$ ~i~ $(1 \le C_i \le 10^7)$ ~(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$ ~2^{63}-1~ in total.

Sample Input

Sample Output

Explanation of Output for Sample Input

Bruce can pack book 1 into container 1 with a cost of $(3-4)^2=1$ ~(3-4)^2=1~, book 2 into container 2 with a cost of $(4-4)^2=0$ ~(4-4)^2=0~, book 3 and book 4 into container 3 with a cost of $(2+1+1-4)^2=0$ ~(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$ ~(4-4)^2=0~. The total cost is 1.

Comments

42

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 $\mathcal{O}(N)$ ~\mathcal{O}(N)~ or $\mathcal{O}(N \log N)$ ~\mathcal{O}(N \log N)~. Please check this link.