P10299 [CCC 2024 S5] Chocolate Bar Partition

Maxwell has a chocolate bar that he wants to share with his friends. The chocolate bar can be viewed as a $2 \times N$ grid of small squares, and the tastiness of each square is given by a $2 \times N$ integer array $T_{i,j}$. Maxwell wants to divide the entire chocolate bar into several connected components, such that the average tastiness of the squares in each connected component is the same. Maxwell wants to know the maximum number of connected components he can partition the chocolate bar into, under the rules above. A part is considered a connected component if every square in it can be reached by moving up, down, left, or right.

The first line contains a positive integer $N$, representing the length of the chocolate bar. The second line contains $N$ space-separated integers. The $j$-th integer is the tastiness $T_{1,j}$ of the square in row 1 and column $j$. Similarly, the third line contains $N$ space-separated integers. The $j$-th integer is the tastiness $T_{2,j}$ of the square in row 2 and column $j$.

Output one integer, representing the maximum number of connected components Maxwell can cut the chocolate bar into.

**Sample 1 Explanation** Partitioning the chocolate bar into $2$ parts is optimal. One way is to take the single square in the bottom-right corner as one connected component, and the remaining three squares as the second connected component, as shown below.  The average tastiness of each connected component is $5$. **Sample 2 Explanation** One way to partition the chocolate bar with equal averages is shown below:  Note that the average tastiness of each part is $1$. **Constraints** **This problem uses bundled testdata.** For all testdata, it is guaranteed that $1 \leq N \leq 2 \times 10^5$ and $0 \leq T_{i,j} \leq 10^8$. The table below shows the distribution of $15$ points: | Points | Range of $N$ | Range of $T_{i,j}$ | | :-: | :-: | :-: | | $2$ | $N = 2$ | $0 \leq T_{i,j} \leq 5$ | | $2$ | $1 \leq N \leq 8$ | $0 \leq T_{i,j} \leq 20$ | | $1$ | $1 \leq N \leq 20$ | $0 \leq T_{i,j} \leq 20$ | | $2$ | $1 \leq N \leq 100$ | $0 \leq T_{i,j} \leq 20$ | | $2$ | $1 \leq N \leq 1000$ | $0 \leq T_{i,j} \leq 100$ | | $3$ | $1 \leq N \leq 2000$ | $0 \leq T_{i,j} \leq 10^5$ | | $3$ | $1 \leq N \leq 2 \times 10^5$ | $0 \leq T_{i,j} \leq 10^8$ | Translated by ChatGPT 5