COCI '14 Contest 2 #5 Šuma

View as PDF

Submit solution

Points: 20 (partial)
Time limit: 1.0s
Memory limit: 128M

Problem type

Mirko lives in a big enchanted forest where trees are very tall and grow really quickly. That forest can be represented as an N \times N matrix where each field contains one tree.

Mirko is very fond of the trees in the enchanted forest. He spent years observing them and for each tree measured how many meters it grew in a year. The trees grow continuously. In other words, if the tree grows 5 meters in a year, it will grow 2.5 meters in half a year.

Apart from trees, Mirko likes mushrooms from the enchanted forest. Sometimes, he eats suspicious colorful mushrooms and starts thinking about peculiar questions. Yesterday, this unfortunate thing happened and he wondered what would be the size of the largest connected group of trees that are all of equal height if the trees continue to grow at the same speed they're growing at that moment.

Mirko quickly measured the current height of all trees in the forest and asked you to answer his question.

Two trees are adjacent if their fields in the matrix share a common edge.
Two trees are connected if there is a sequence of adjacent trees that leads from the first to the second.
A group of trees is connected if every pair of trees in the group is connected.

Input Specification

The first line of input contains the integer N (1 \le N \le 700).

After the first line, N lines follow, each of them containing N integers.

The i^{th} line contains integers h_{ij} (1 \le h_{ij} \le 10^9), the initial height of tree in the i^{th} row and j^{th} column, given in meters.

After that, N more lines follow with N integers.

The i^{th} line contains integers v_{ij} (1 \le v_{ij} \le 10^6), the growth speed of the tree in the i^{th} row and j^{th} column, given in meters.

Warning: Please use faster input methods because the amount of input is very large. (For example, use scanf instead of cin in C++ or BufferedReader instead of Scanner in Java).

Output Specification

The first and only line of output must contain the required number from the task.


In test cases worth 30% of total points, it will hold 1 \le N \le 70.

Sample Input 1

1 2 3
3 2 2
5 2 1
3 2 1
1 2 1
1 2 3

Sample Output 1


Sample Input 2

3 1
3 3
2 5
2 5

Sample Output 2


Explanation of Output for Sample Input 2

After 8 months (two thirds of a year), the trees located at (0, 0), (0, 1) and (1, 0) will be \dfrac{13}{3} meters in height.


  • 0
    FatalEagle  commented on Nov. 30, 2014, 3:56 a.m.

    MLE every day