Castillo de arena
Descripción
OCI-Cub está jugando en una playa de arena. Hace un castillo de arena. El castillo de arena hecho por OCI-Cubo está contenido en una región rectangular en la playa de arena. La región rectangular consta de celdas de filas horizontales y W columnas verticales. La celda en la fila i-ésima () desde el norte y la columna j-ésima () desde el oeste tiene altura . Obsérvese que los valores de son diferentes entre sí.
Para el castillo de arena, OCI-Cub realizó las siguientes acciones.
En primer lugar, OCI-Cub eligió una celda, y comenzó a moverse desde la celda elegida.
A continuación, se movió desde la celda actual a una celda adyacente en una de las cuatro direcciones. Tiene que moverse a una celda que esté más abajo que la celda actual. Repitió esto cero o más veces.
Por último, si vemos las celdas que ha visitado desde arriba, las celdas forman un rectángulo.
Tarea
Dada la información de la altura de cada celda, escribe un programa que calcule el número de rectángulos posibles formados por las celdas visitadas por OCI-Cub.
Entrada
Lea los siguientes datos de la entrada estándar. Los valores dados son todos enteros.
---
---
.
.
.
A_{H,W}~
Salida
Escriba una línea en la salida estándar. La salida debe contener el número de posibles rectángulos formados por las celdas visitadas por OCI-Cub.
Restricciones
- .
- .
- × .
- ().
- ≠ (, , , , ≠ )).
Subtareas
- (9 puntos) = .
- (10 puntos) × .
- (5 puntos) × .
- (56 puntos) × .
- (20 puntos) Sin restricciones adicionales.
Ejemplo de entrada y salida
Ejemplo de Entrada #1
1 5
2 4 7 1 5
Ejemplo de Salida #1
10
Dado que hay rectángulos posibles formados por las celdas visitadas por OCI-Cub, salida
Este ejemplo de entrada satisface las restricciones de todas las subtareas.
Ejemplo de Entrada #2
3 2
18 10
19 12
17 13
Ejemplo de Salida #2
15
Como hay rectángulos posibles formados por las celdas visitadas por JOI-kun, salida
Esta entrada de ejemplo satisface las restricciones de las subtareas 2, 3, 4, 5.
Ejemplo de Entrada #3
3 5
83 47 36 38 40
13 10 26 68 67
15 19 20 70 90
Ejemplo de Salida #3
65
Por ejemplo, los siguientes rectángulos pueden estar formados por las celdas visitadas por OCI-Cub. Como hay rectángulos posibles en total, salida .
Este ejemplo de entrada satisface las restricciones de las subtareas 2, 3, 4, 5.
Comments
Reenviar la solución error en caso de pruebas de la primera subtarea