ページが読み込まれませんか？ こちらをクリックすると直るかもしれません。
Placeholder

#5856
サブタスク

땅따먹기 (Land Division) 2s 1024MB

問題

JOI 국가는 세로 H 행, 가로 W 열의 격자 모양으로 구분 된 직사각형 형태를 하고 있다.

JOI 국가의 종 방향은 남북 방향에 평행하고 횡 방향은 동서 방향에 평행하다.

북쪽에서 i 행째 ( 1 ≤ i ≤ H ), 서쪽에서 j 열째 ( 1 ≤ j ≤ W )의 칸의 인구는 A_{ i, j}명이다.

JOI 국가에서는, 행정의 효율화를 위해, 다음의 조건을 만족하는 경계선을 1 개 이상 빼서,

나라 전체를 2 개 이상의 지구로 분할하기로 했다.

경계선은 격자 칸의 경계에 있다.

경계선은 JOI 국가의 북쪽 끝에서 남쪽 끝 또는 JOI 국가의 동쪽 끝에서 서쪽 끝을 연결하는 선분이다.

JOI 국가의 각 칸의 인구가 주어지므로 가능한 분할 방법 중

모든 지구의 인구가 같아지는 분할 방법은 몇 가지가 있는 지를 출력하는 프로그램을 작성하라.


入力

입력은 다음 형식으로 표준 입력에서 제공됩니다.

H W

A_{1,1} A_{1,2} … A_{1,W}

A_{2,1} A_{2,2} … A_{2,W}

:

A_{H,1} A_{H,2} … A_{H,W}

[제한]

1 ≦ H ≦ 50．

1 ≦ W ≦ 50．

1 ≦ A_{i,j} ≦ 100\,000 (1 ≦ i ≦ H, 1 ≦ j ≦ W)．

모든 입력은 정수이다.


出力

표준 출력에 모든 지구의 인구가 같아지는 분할 방법은 몇 가지가 있는지를 한 줄로 출력하라 .


部分問題

番号 点数 条件
#112点

H=1

#226点

H ≤ 6 , W ≤ 6

#362点

추가 제약은 없다


例題 #1

2 3
10 10 20
10 10 20
3

아래 그림과 같이 모든 지구의 인구가 같아지는 분할 방법은  3가지가 있으므로 3을 출력한다.

이 입력 예는 작은 문제  2,3  의 제약 조건을 충족합니다.


例題 #2

1 4
2 1 1 2
2

例題 #3

3 3
2 9 4
7 5 3
6 1 8
2

例題 #4

1 1
10000
0


出典

JOI 2022 예선2

ログインしないとコードを書けません。