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.

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)