Maximum Connected Blocks Partitioning

Maxwell wants to share a chocolate bar with his friends. The chocolate bar is composed of 2×N small squares. The deliciousness of each square is given by a 2×N integer matrix \(T_{i,j}\). He wants to partition the entire chocolate into several connected blocks such that the average deliciousness of the squares in each block is the same. Two squares are considered connected if you can move from one to the other by up, down, left, or right moves. Determine the maximum number of connected blocks into which the chocolate bar can be partitioned under this condition.

Explanation:

Let \(S = \sum_{i=1}^{2}\sum_{j=1}^{N} T_{i,j}\) be the total deliciousness and let the global average be \(g = \frac{S}{2N}\). For any connected block with \(k\) squares, if its sum of deliciousness is \(S_b\) then the condition that its average equals \(g\) is equivalent to \[ \frac{S_b}{k} = g \quad\Longleftrightarrow\quad S_b = k\,g. \] This can be rephrased by letting \(d_{i,j} = T_{i,j} - g\) so that every block must have a total \(d\)-value of zero.

Because the chocolate bar has only two rows, a natural idea is to cut vertically between columns whenever possible. Define a column difference as \[ D_j = (T_{1,j} + T_{2,j}) - 2g. \] If you consider the columns from \(1\) to \(N\) and compute the cumulative sum of \(D_j\), every time this sum becomes zero you may insert a vertical cut. In other words, if columns \(l\) to \(r\) satisfy \[ \sum_{j=l}^{r} D_j = 0, \] then those columns can form a block.

Furthermore, if in a block (which is a contiguous set of columns) there exists a column for which both cells are balanced (i.e. they satisfy \(T_{1,j} = T_{2,j} = g\)), then that column itself can be split horizontally into two connected blocks (since splitting a 2×1 column vertically yields two isolated squares, each with an average equal to \(g\)).

Thus, the maximum number of blocks equals the number of vertical segments (obtained by making vertical cuts at every column index \(j\) where the cumulative sum becomes zero) plus the number of segments in which there is at least one balanced column.

More formally, let us process the columns from 1 to N and accumulate \[ \text{cum} += (T_{1,j}+T_{2,j} - 2g). \] Whenever \(\text{cum} = 0\), we have identified a segment. If at least one column in this segment satisfies \(T_{1,j} = T_{2,j} = g\), then in that segment a horizontal cut is possible, thereby increasing the block count by one. The final answer is then:

[ \text{answer} = (\text{number of segments}) + (\text{number of segments having a balanced column}). ]

Note: Since \(g\) may not be an integer, a column can be balanced only if both its deliciousness values exactly equal \(g\); otherwise, a horizontal split is not possible in that segment.

inputFormat

The first line contains an integer \(N\) (number of columns).
The next two lines each contain \(N\) space-separated integers.
The first of these lines represents the deliciousness values of the first row \(T_{1,1}, T_{1,2}, \ldots, T_{1,N}\), and the second represents the second row \(T_{2,1}, T_{2,2}, \ldots, T_{2,N}\).

outputFormat

Output a single integer representing the maximum number of connected blocks into which the chocolate bar can be partitioned such that each block has the same average deliciousness.

sample

3
3 2 1
1 2 3

4