Problem Description

Farmer John’s pasture can be seen as a square grid made up of $N \times N$ square cells ($1 \leq N \leq 500$), like a huge chessboard. Because of soil variability, the grass in some cells may be greener. Each cell $(i,j)$ is described by an integer greenness value $G(i,j)$, in the range $1 \ldots 200$.

Farmer John wants to take a photo of a submatrix of his pasture. He wants to make sure this submatrix looks green enough, but not too green, so he decides to photograph a submatrix whose minimum value of $G$ is exactly $100$. Please help him find how many different photos he can take. The largest submatrix can be the entire pasture, and the smallest can be just one cell (there are $N^2(N+1)^2/4$ different submatrices in total—note that this number may not fit in a $32$-bit integer type, so you may need to use a $64$-bit integer type, such as long long in C++).

Input Format

The first line contains $N$. The next $N$ lines each contain $N$ integers, representing the values $G(i,j)$ of the $N \times N$ pasture.

Output Format

Output the number of different photos Farmer John can take, i.e., the number of submatrices whose minimum greenness value is equal to $100$.

Note that the integer size in this problem may require using a $64$-bit integer type (for example, long long in C/C++).

3
57 120 87
200 100 150
2 141 135

8

Hint

Test Point Properties:

• For $50\%$ of the testdata, $N \leq 200$.
• For the other $50\%$ of the testdata, there are no additional constraints.

Problem by: Brian Dean

Translated by ChatGPT 5