Armchairs
Contest: Educational Codeforces Round 109 (Rated for Div. 2)
Difficulty rating: 1800
Tags: dp, flows, graph matchings, greedy

There are $$$n$$$ armchairs, numbered from $$$1$$$ to $$$n$$$ from left to right. Some armchairs are occupied by people (at most one person per armchair), others are not. The number of occupied armchairs is not greater than $$$\frac{n}{2}$$$.

For some reason, you would like to tell people to move from their armchairs to some other ones. If the $$$i$$$-th armchair is occupied by someone and the $$$j$$$-th armchair is not, you can tell the person sitting in the $$$i$$$-th armchair to move to the $$$j$$$-th armchair. The time it takes a person to move from the $$$i$$$-th armchair to the $$$j$$$-th one is $$$|i - j|$$$ minutes. You may perform this operation any number of times, but these operations must be done sequentially, i. e. you cannot tell a person to move until the person you asked to move in the last operation has finished moving to their destination armchair.

You want to achieve the following situation: every seat that was initially occupied must be free. What is the minimum time you need to do it?

Input format:
The first line contains one integer $$$n$$$ ($$$2 \le n \le 5000$$$) — the number of armchairs.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 1$$$). $$$a_i = 1$$$ means that the $$$i$$$-th armchair is initially occupied, $$$a_i = 0$$$ means that it is initially free. The number of occupied armchairs is at most $$$\frac{n}{2}$$$.

Output format:
Print one integer — the minimum number of minutes you have to spend to achieve the following situation: every seat that was initially occupied must be free.

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

Note:
In the first test, you can perform the following sequence:

1. ask a person to move from armchair $$$1$$$ to armchair $$$2$$$, it takes $$$1$$$ minute;
2. ask a person to move from armchair $$$7$$$ to armchair $$$6$$$, it takes $$$1$$$ minute;
3. ask a person to move from armchair $$$4$$$ to armchair $$$5$$$, it takes $$$1$$$ minute.

In the second test, you can perform the following sequence:

1. ask a person to move from armchair $$$1$$$ to armchair $$$4$$$, it takes $$$3$$$ minutes;
2. ask a person to move from armchair $$$2$$$ to armchair $$$6$$$, it takes $$$4$$$ minutes;
3. ask a person to move from armchair $$$4$$$ to armchair $$$5$$$, it takes $$$1$$$ minute;
4. ask a person to move from armchair $$$3$$$ to armchair $$$4$$$, it takes $$$1$$$ minute.

In the third test, no seat is occupied so your goal is achieved instantly.

Example input:
7
1 0 0 1 0 0 1

Example output:
3

Example input:
6
1 1 1 0 0 0

Example output:
9

Editorial:
Let's say that the starting position of people are $$$x_1, x_2, \dots, x_k$$$ (in sorted order) and ending positions of people are $$$y_1, y_2, \dots, y_k$$$ (also in sorted order). It's always optimal to match these starting and ending positions in sorted order: the leftmost starting position is matched with the leftmost ending, the second starting position is matched with the second ending, and so on. To prove it, suppose that position $$$X_1$$$ is matched with $$$Y_2$$$, position $$$X_2$$$ is matched with $$$Y_1$$$, $$$X_1 \le X_2$$$ and $$$Y_1 \le Y_2$$$. If both persons go to the left or to the right, it means that either $$$X_1 \le X_2 \le Y_1 \le Y_2$$$ or $$$Y_1 \le Y_2 \le X_1 \le X_2$$$, so nothing changes if we swap the matched positions. If, instead, the person that goes from $$$X_1$$$ to $$$Y_2$$$ goes to the right, and the person that goes from $$$X_2$$$ to $$$Y_1$$$ goes to the left, the segment $$$[\max(X_1, Y_1), \min(X_2, Y_2)]$$$ belongs to both paths, and swapping the matched pairs removes this segment from both paths (and decreases the total time). So, if the order of starting positions is sorted and the order of ending positions is sorted, these positions should be matched exactly in those order.
Using this fact, we can implement the following dynamic programming: let $$$dp_{i, j}$$$ be the minimum time if we considered $$$i$$$ first positions and picked $$$j$$$ of them as the ending ones. Transitions are the following: we either take the current position as the ending one (if it's not a starting one), match it with the $$$j$$$-th starting position and go to $$$dp_{i+1, j+1}$$$, or we skip the current position and go to $$$dp_{i+1,j}$$$. It works in $$$O(n^2)$$$ since it has up to $$$O(n^2)$$$ states and just up to $$$2$$$ transitions from each state.