Problem
El pasto del granjero John se puede considerar como una cuadrícula
NxN (
\(1<=N<=500\)) de celdas cuadradas con hierba (como un gran tablero de ajedrez). Debido a la variabilidad del suelo, la hierba en algunas celdas es más verde que en otras. Cada celda
(i,j) se describe con un número entero: el nivel de verdor
G(i,j), en el intervalo
\ (1…200\).
El granjero John quiere tomar una foto de una subcuadrícula rectangular de su pasto. Quiere que el mínimo de G en su foto sea nítida 100. Ayúdalo a contar cuántas fotos diferentes puede tomar. La subcuadrícula puede variar en tamaño desde todo el pasto hasta una celda. Hay \(N^2(N+1)^2/4\) diferentes subredes, use un número entero de 64 bits (como < code>long larga en C++).
Entrada
La primera línea contiene
N. Cada una de las siguientes
N líneas contiene
N números enteros y juntas describen las magnitudes
G(i,j) ; ;para pasto
NхN .
Impresión
Muestra la cantidad de fotografías diferentes que Farmer John puede tomar, es decir el número de subredes rectangulares en las que el nivel mínimo de "verdor" exactamente
100.
Tenga en cuenta que la respuesta requiere una variable entera de 64 bits de tipo long long en C++.
Ejemplos
| # |
Entrada |
Salida |
| 1 |
3
57 120 87
200 100 150
2 141 135
| 8 |