Problem
O pasto do fazendeiro John pode ser pensado como uma grade
NxN (
\(1<=N<=500\)) de células quadradas com grama (como um grande tabuleiro de xadrez). Devido à variabilidade do solo, a grama em algumas células é mais verde do que em outras. Cada célula
(i,j) é descrita por um inteiro - o nível de verde
G(i,j), no intervalo
\ (1…200\).
O fazendeiro John quer tirar uma foto de uma sub-grade retangular de seu pasto. Ele quer que o mínimo de G em sua foto seja nítido 100. Ajude-o a contar quantas fotos diferentes ele pode tirar. A subgrade pode variar em tamanho, desde o pasto inteiro até uma célula. Existem \(N^2(N+1)^2/4\) diferentes sub-redes, use um inteiro de 64 bits (como < code>long longo em C++).
Entrada
A primeira linha contém
N. Cada um dos seguintes
N linhas contém
N inteiros e juntos eles descrevem as magnitudes
G(i,j) ; ;para pastagem
NхN .
Impressão
Imprima o número de fotografias diferentes que o fazendeiro John pode tirar, ou seja, o número de sub-redes retangulares em que o nível mínimo de "verde" exatamente
100.
Observe que a resposta requer uma variável inteira de 64 bits do tipo long long em C++.
Exemplos
| # |
Entrada |
Saída |
| 1 |
3
57 120 87
200 100 150
2 141 135
| 8 |