Battle Lemmings
Contest: Codeforces Round 672 (Div. 2)
Difficulty rating: 2500
Tags: dp, greedy

A lighthouse keeper Peter commands an army of $$$n$$$ battle lemmings. He ordered his army to stand in a line and numbered the lemmings from $$$1$$$ to $$$n$$$ from left to right. Some of the lemmings hold shields. Each lemming cannot hold more than one shield.

The more protected Peter's army is, the better. To calculate the protection of the army, he finds the number of protected pairs of lemmings, that is such pairs that both lemmings in the pair don't hold a shield, but there is a lemming with a shield between them.

Now it's time to prepare for defence and increase the protection of the army. To do this, Peter can give orders. He chooses a lemming with a shield and gives him one of the two orders:

- give the shield to the left neighbor if it exists and doesn't have a shield;
- give the shield to the right neighbor if it exists and doesn't have a shield.

In one second Peter can give exactly one order.

It's not clear how much time Peter has before the defence. So he decided to determine the maximal value of army protection for each $$$k$$$ from $$$0$$$ to $$$\frac{n(n-1)}2$$$, if he gives no more that $$$k$$$ orders. Help Peter to calculate it!

Input format:
First line contains a single integer $$$n$$$ ($$$1 \le n \le 80$$$), the number of lemmings in Peter's army.

Second line contains $$$n$$$ integers $$$a_i$$$ ($$$0 \le a_i \le 1$$$). If $$$a_i = 1$$$, then the $$$i$$$-th lemming has a shield, otherwise $$$a_i = 0$$$.

Output format:
Print $$$\frac{n(n-1)}2 + 1$$$ numbers, the greatest possible protection after no more than $$$0, 1, \dots, \frac{n(n-1)}2$$$ orders.

Constraints:
Time limit: 2.0 s
Memory limit: 512.0 MB

Note:
Consider the first example.

The protection is initially equal to zero, because for each pair of lemmings without shields there is no lemmings with shield.

In one second Peter can order the first lemming give his shield to the right neighbor. In this case, the protection is two, as there are two protected pairs of lemmings, $$$(1, 3)$$$ and $$$(1, 4)$$$.

In two seconds Peter can act in the following way. First, he orders the fifth lemming to give a shield to the left neighbor. Then, he orders the first lemming to give a shield to the right neighbor. In this case Peter has three protected pairs of lemmings — $$$(1, 3)$$$, $$$(1, 5)$$$ and $$$(3, 5)$$$.

You can make sure that it's impossible to give orders in such a way that the protection becomes greater than three.

Example input:
5
1 0 0 0 1

Example output:
0 2 3 3 3 3 3 3 3 3 3

Example input:
12
0 0 0 0 1 1 1 1 0 1 1 0

Example output:
9 12 13 14 14 14 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15

Editorial:
First, let us denote $$$f(A)$$$ as a conversion of the original sequence of $$$A$$$. In the beginning, we will write down the number of zeros before the the first one. Then, we write down the number of zeros standing between the first and second ones, then — between the second and third ones, and so on. For example, $$$f(011000101100) = \{1, 0, 3, 1, 0, 2\}$$$, because there is one zero before the first one, there are no zeros between the first and second ones, there are three zeros between the second and third ones, etc.  d. It is not difficult to see that the original sequence $$$A$$$ can be unambiguously recovered with $$$f(A)$$$.
Now, let us consider how $$$f(A)$$$ will change if we change two different adjacent elements in the original $$$A$$$ sequence. In this case, two neighboring numbers will change in $$$f(A)$$$, one of which will decrease by one and the other — will increase by one. The reversed statement is also true: if we choose two neighboring numbers in $$$f(A)$$$, one of them will increase by one, and the other — will decrease by one so that they both remain non-negative, this operation will correspond to an exchange of two neighboring elements in $$$A$$$. Let us name this operation (choosing two neighboring numbers, increasing one of them by one and reducing the other by one). pouring.
Let us consider such a task. We have two arrays $$$A = \{a_1, a_2, \dots, a_k\}$$$ and $$$B = \{b_1, b_2, \dots, b_k\}$$$. We have to calculate the minimum amount of pouring operations we can turn $$$A$$$ into $$$B$$$. (Obviously, the sum of the numbers in $$$A$$$ and in $$$B$$$ must be the same.) To solve this, let's try to split the array into two "barriers", standing after $$$i$$$-th position. Then, the $$$A$$$ array is split into two parts: the left (elements from $$$1$$$ to $$$i$$$) and the right (elements from $$$i+1$$$ to $$$n$$$). For the left part of the $$$A$$$ array to have the same number of elements as in $$$B$$$, you need $$$g_{A, B}(i) = \left|\sum_{j=1}^{i} a_i - \sum_{j=1}^i b_i\right|$$$ pouring operations involving $$$i$$$ and $$$i+1$$$ elements. To sum up the number of necessary pouring operations for each pair of neighboring elements, you have to sum $$$g_{A,B}(i)$$$ for all $$$i$$$ from $$$1$$$ to $$$n-1$$$. It can be shown that the sum obtained will be the required number of pouring operations, because  since it is equal to zero only in case of equal arrays, and each pouring operation will reduce it by no more than $$$1$$$ (and there is always a transfusion that reduces this sum by $$$1$$$).
So, this subtask has been sorted out, let's move on. We have to learn how to read security for the sequence $$$A$$$, knowing $$$f(A) = \{f_1, f_2, \dots, f_k\}$$$. It is not difficult to see that it is equal to $$$$$$p(A) = \sum_{1 \le i < j \le k} f_i\cdot f_j = \frac 12 \left( \sum_{1 \le i, j \le k} f_i\cdot f_j - \sum_{i=1}^k f_i^2 \right) = \frac 12 \left( \left(\sum_{i=1}^k f_i \right)^2 - \sum_{i=1}^k f_i^2 \right).$$$$$$ We already know the value of $$$\sum_{i=1}^k f_i$$$: it is equal to the number of zeroes in $$$A$$$. So, we have to minimize $$$\sum_{i=1}^k f_i^2$$$.
Now we can finally get down to the task. To do this, let's try to build an optimal sequence of $$$f(A) = \{f_1, f_2, \dots, f_k\}$$$ by applying no more than $$$k$$$ of transfusions. Of course, we need to use the dynamic programming of $$$dp_{i,\ s,\ k}$$$. This means that we have looked at the first $$$i$$$ elements in $$$f(A)$$$ and done with $$$k$$$ pouring operations so that $$$\sum_{i=1}^k f_i$$$ equals $$$s$$$. The DP itself will store the minimum possible value of $$$\sum_{i=1}^k f_i^2$$$.
To get the answer we need to refer to $$$dp_{i,\ c_0,\ k}$$$ where $$$c_0$$$ — is the number of zeros in the original sequence. And to recalculate the dynamics of $$$dp_{i,\ s,\ k}$$$ we have to go through what $$$f_{i+1}$$$ will be as a result. Let it be $$$h$$$. Then, the answer recovery happens in the following way:
$$$$$$dp_{i+1,\ s + h,\ k + \left|z_i - (s + h)\right|} \text{min=} dp_{i,\ s,\ k} + h^2.$$$$$$
Here $$$z_i$$$ denotes $$$\sum_{j=1}^i f_i$$$ in the original sequence $$$f(A)$$$.
The total asymptotic is $$$O(n^5)$$$ in time and $$$O(n^4)$$$ in memory, although with a correct implementation the constant is very small (the author's solution works for $$$\frac{n^5}{27}$$$). In this task, there are solutions for $$$O(n^4\log n)$$$, but I will not describe them here.