IOI '14 - Taipei, Taiwan
Cutting a square from a material
Jian-Jia has a piece of metal material and he wants to cut a square out
of it. The material consists of by
unit grids and Jian-Jia can
only cut the material along grid boundary. Each grid is either usable or
defective, and Jian-Jia wants to cut the largest possible square from
the material without any defective grids. After determining the maximum
size of the square, Jian-Jia also wants to know how many ways he can cut
the largest square from this material. Finally Jian-Jia will report the
product of the maximum size and the number of possible ways.
Example
Consider the by
material in the following figure. The black grids
are defective. The largest square Jian-Jia can cut from the material is
by
, and there are two ways to cut it – the red square and the green
square. Jian-Jia will report the product of
and
, which is
.
![](https://static.dmoj.ca/data/peg/ioi1401/ioi1401.png)
Your task is to find the size of largest squares in the material, count the number of ways to cut them, and report the product of the size and the number.
Input Specification
- Line 1: the size of the material
;
- Line
:
- Each line has
integers. A
means the grid is useful and a
means the grid is defective.
- Each line has
Output Specification
You must output one integer – the product of the size of largest square in the material, and the number of possible locations in the material.
Sample Input 1
6
1 0 1 0 1 0
0 1 0 1 0 1
1 0 1 0 1 0
0 1 0 1 0 1
1 0 1 0 1 0
0 1 0 1 0 1
Sample Output 1
18
Sample Input 2
6
0 1 1 1 1 0
1 0 1 1 1 1
0 1 1 1 1 1
1 1 0 1 1 1
1 1 1 1 0 1
1 1 0 1 1 1
Sample Output 2
6
Constraints
Subtask 1 [10%]
In any by
material grids section there will be at least one defective grid.
Comments