살구 수확량

면접 대비

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

요약

n×m 표에서 합이 S보다 작은 정사각형 부분표의 개수를 셉니다.

난이도: 쉬움10점 중 3점
유형: 누적 합, 완전 탐색
정답자: 아직 제출이 없습니다

문제

$n \times m$ 크기의 표에 수가 채워져 있다. 왕은 기준값 $S$ 를 정했고, 밭의 모든 $k \times k$ 정사각형은 수확량이 $S$ 이상이어야 한다. 정사각형은 나무 한 그루로만 이루어질 수 있다. 브리코 1세는 농학자들의 보고를 의심하여, 이 기준을 충족하지 못하는 정사각형, 즉 합이 $S$ 보다 작은 정사각형의 개수를 구하라고 명령했다.

입력

첫 줄에 세 정수 $n$ , $m$ , $S$ 가 주어진다. 이는 실험용 살구 밭의 크기와 왕이 정한 값이다. 이어지는 $n$ 개 줄에는 각각 $m$ 개의 수가 주어지며, $a_{ij}$ 는 $i$ 행 $j$ 열 나무에 열린 살구의 개수이다 ( $1 \le n, m \le 30$ ; $0 \le S \le 10^{9}$ ; $0 \le a_{ij} \le 10^{7}$ ).

출력

기준을 충족하지 못하는 정사각형의 개수를 나타내는 정수 하나를 출력한다.

예제2

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