초콜릿 바 분할

시간 제한1초메모리 제한1024 MB

요약

2×N 격자의 맛 값을 같은 평균을 가진 연결된 조각들로 나눌 때, 만들 수 있는 조각의 최대 개수를 구합니다.

난이도: 보통10점 중 6점
유형: 누적 합, 해시맵, 행렬
정답자: 아직 제출이 없습니다

문제

Maxwell은 친구들과 나누어 먹으려고 초콜릿 바를 가지고 있다. 초콜릿 바는 정수로 이루어진 $2 \times N$ 배열 $T_{i,j}$ 로 표현되며, 각 값은 한 칸의 맛을 나타낸다. Maxwell은 모든 조각의 평균(mean) 맛이 같아지도록 바 전체를 연결된 조각들로 나누려고 한다. 나눌 수 있는 조각 수의 최댓값을 구하라.

조각이 연결되어 있다는 것은 상하좌우로 이동해서 그 조각의 모든 칸을 방문할 수 있다는 뜻이다.

입력

첫째 줄에 양의 정수 $N$ 이 주어진다. $N$ 은 초콜릿 바의 길이이다.

둘째 줄에는 공백으로 구분된 $N$ 개의 정수가 주어진다. 왼쪽에서 $j$ 번째 정수가 $T_{1,j}$ 이다.

셋째 줄에는 공백으로 구분된 $N$ 개의 정수가 주어진다. 왼쪽에서 $j$ 번째 정수가 $T_{2,j}$ 이다.

출력

Maxwell이 초콜릿 바를 연결된 조각들로 나눌 수 있는 최대 조각 수를 정수 하나로 출력한다.

예제2

예제 1
입력
```
2
5 4
6 5
```
예상 출력
```
2
```
예제 2
입력
```
5
1 0 1 2 0
0 2 0 3 1
```
예상 출력
```
5
```