Corner Subgrid Count.

Points: 100 (partial)

Time limit: 2.0s

Memory limit: 512M

Author:

Problem type

Allowed languages

Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Java, JS, Kotlin, Lisp, Lua, ObjC, OCaml, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, ~~Swift~~, TCL, Text, Turing, VB, Zig

Se te da una cuadrícula de $n \times n$ ~n \times n~ donde cada cuadrado es negro o blanco. Un subcuadrículo se considera «hermoso» si su altura y anchura son al menos dos y todas sus esquinas son negras. ¿Cuántos subcuadrículos «hermosos» hay en la cuadrícula dada?

Entrada

La primera línea de entrada contiene un entero $n$ ~n~: el tamaño de la cuadrícula.
Luego hay $n$ ~n~ líneas que describen la cuadrícula: $1$ ~1~ significa que un cuadrado es negro y $0$ ~0~ que es blanco.

Salida

Imprime el número de subcuadrículos «hermosos».

Restricciones

$1 \leq n \leq 3000$ ~1 \leq n \leq 3000~

Ejemplo de Entrada

Ejemplo de Salida

Comments

There are no comments at the moment.