Problem
Le pâturage du fermier John peut être considéré comme une grille
NxN (
\(1<=N<=500\)) de cellules carrées avec de l'herbe (comme un grand échiquier). En raison de la variabilité du sol, l'herbe dans certaines cellules est plus verte que dans d'autres. Chaque cellule
(i,j) est décrite par un entier - le niveau de verdure
G(i,j), dans l'intervalle
\ (1…200\).
Le fermier John veut prendre une photo d'une sous-grille rectangulaire de son pâturage. Il veut que le minimum de G sur sa photo soit net 100. Aidez-le à compter le nombre de photos différentes qu'il peut prendre. La sous-grille peut varier en taille de l'ensemble du pâturage à une cellule. Il existe \(N^2(N+1)^2/4\) différents sous-réseaux, utilisez un entier 64 bits (comme < code>long long en C++).
Entrée
La première ligne contient
N. Chacune des
N lignes suivantes contient
N entiers et ensemble, elles décrivent les magnitudes
G(i,j) ; ;pour le pâturage
NхN .
Mentions légales
Indiquez le nombre de photographies différentes que Farmer John peut prendre, c'est-à-dire le nombre de sous-réseaux rectangulaires dans lesquels le niveau minimum de "verdure" exactement
100.
Notez que la réponse nécessite une variable entière 64 bits de type long long en C++.
Exemples
| # |
Entrée |
Sortie |
| 1 |
3
57 120 87
200 100 150
2 141 135
| 8 |