Region of Twos

$C_{i,j}=2$인 것은 $A_i=B_j=1$인 것과 같다.

$A$에서 연속한 $1$의 한 구간과 $B$에서 연속한 $1$의 한 구간을 고르면, 두 구간의 데카르트 곱에 해당하는 칸들은 모두 $2$이고 하나의 직사각형 연결 요소를 이룬다. 서로 다른 연속 구간 사이에는 반드시 $0$이 끼어 있으므로 서로 연결될 수 없다.

따라서 $A$의 최장 연속 $1$ 구간 길이를 $L_A$, $B$의 최장 연속 $1$ 구간 길이를 $L_B$라고 하면 정답은 $L_A L_B$이다. 두 수열을 한 번씩 순회하면 되므로 시간 복잡도는 $O(N+M)$이다. Solution written by GPT5.6