P9900 『PG2』Eliminate Carrots B

There are $n\times 2$ carrots arranged in two columns. Carrots are either white or red. We use $a_{i,j}=0/1$ to represent whether the carrot in row $i$, column $j$ is white or red. Each time, you may pay a cost of $1$ to choose a position that currently has a carrot, and remove all carrots in the 4-connected maximal connected component consisting of carrots of the same color as that chosen carrot. After that, if a carrot is in row $i$ and the corresponding position in row $i-1$ has no carrot, then it will fall to row $i-1$. Also, you may pay a cost that is initially $0$ to choose $k=1/2$ and shift all carrots in column $k$ upward ($a_{i,k}\to a_{i+1,k}$), and place a red carrot, i.e. $1$, into row $1$, column $k$ ($1\to a_{1,k}$). After this, the cost of this operation increases by $1$ each time it is used. Find the minimum total cost to remove all carrots.

The first line contains a positive integer $n$, the number of rows of carrots. The next $n$ lines each contain two integers, which are $a_{i,1},a_{i,2}$.

Output one integer in one line, representing your answer.

For all test points, $a_{i,j}\in \{0,1\}$, $1\leq n\leq 5\times 10^6$, and it is guaranteed that $a_{i,1}\neq a_{i,2}$. **This problem uses bundled tests.** $\sf subtask \ 1: n\leq10 \ \ \ \ \ \ \ \ \ \ \ 30pts $ $\sf subtask \ 2: n\leq100 \ \ \ \ \ \ \ \ \ 20 pts$ $\sf subtask \ 3: n\leq5000 \ \ \ \ \ \ \ 20 pts$ $\sf subtask \ 4: n\leq5000000 \ 30pts$ Translated by ChatGPT 5