P7410 [USACO21FEB] Just Green Enough S

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++).

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 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++).

#### 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