### IOI '14 - Taipei, Taiwan

## Square

### 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 `n` by `n` 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 6 by 6 material in the following figure. The black grids are defective. The largest square Jian-Jia can cut from the material is 3 by 3, and there are two ways to cut it – the red square and the green square. Jian-Jan will report the product of 3 and 2, which is 6.

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 Format

- Line 1: the size of the material
`n`; - Line 2, …,
`n`+ 1:- Each line has
`n`integers. A 1 means the grid is useful and a 0 means the grid is defective.

- Each line has

### Output Format

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

### Subtask 1 [10% of points]

- 1 ≤
`n`≤ 100 - In any 2 by 2 material grids section there will be at least one defective grid.

### Subtask 2 [20% of points]

- 1 ≤
`n`≤ 500

### Subtask 3 [70% of points]

- 1 ≤
`n`≤ 1000

All Submissions

Best Solutions

**Point Value:** 12 (partial)

**Time Limit:** 2.00s

**Memory Limit:** 64M

**Added:** Jun 25, 2014

**Languages Allowed:**

C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

## Comments (Search)

It's quiet in here...