문제
농부 창호의 목초지는 N x N 격자 조각 형태로 이루어져 있다. 각 i행, j열 조각은 G(i,j) 초록레벨을 가지고 있으며 초록레벨은 1~200 사이의 값을 가진다.
농부 창호는 초록색을 너무 바라봐서 적당히 초록한 곳을 보고 싶어졌기에, 초록레벨의 최소 값이 정확히 100이 되는 부분 직사각형 격자를 선택하고 싶다.
부분 직사각형의 최소 초록레벨이 정확히 100인 경우의 수를 출력하라.
입력
첫 번째 줄에 목초지 격자의 크기 N이 주어진다. ( 1 <= N <= 500 )
다음 N줄에 걸쳐 N개의 초록레벨 G(i,j)이 주어진다. ( 1 <= G(i,j) <= 200 )
출력
농부 창호가 고를 수 있는 최소 초록레벨이 정확히 100인 부분 직사각형을 만드는 경우의 수를 출력한다.
(부분 직시각형의 경우는 모두 N^2 * (N+1)^2 / 4 의 경우의 수가 있으며 이는 C++의 경우 long long 자료형이 필요하다.)
예제1
입력
3
57 120 87
200 100 150
2 141 135
출력
8
출처
USACO 2021 February Silver