DMOPC '22 Contest 2 P6 - Yogyakarta Elevators

View as PDF

Submit solution

Points: 25 (partial)
Time limit: 2.0s
Memory limit: 256M

Problem types

At IOI 2022, Team Canada encountered a mystery with the hotel elevators. Puzzled, they have asked you (their tour guide) to solve it for them.

The elevator system of the hotel can be viewed as a 2-D grid E with N floors and M elevators. The floors are numbered 1 to N from bottom to top and the elevators are numbered 1 to M from left to right. For each floor i, E_{i,j} is 1 if elevator j stops at that floor and 0 if it doesn't. Each elevator can be used to travel between the floors it stops at.

A contiguous subsequence of floors [l, r] is defined as explorable if, starting from any floor in the subsequence, it is possible to reach all other floors in the subsequence while only entering floors numbered from l to r.

Your task is to determine the length of the largest explorable contiguous subsequence of floors.


1 \le N \le 5 \times 10^4

1 \le M \le 500

Subtask 1 [10%]

1 \le N, M \le 300

Subtask 2 [20%]

1 \le M \le 10

Subtask 3 [30%]

1 \le M \le 50

Subtask 4 [40%]

No additional constraints.

Input Specification

The first line contains 2 integers N and M.

The next N lines each contain M characters (0 or 1), the j-th character of the i-th line representing E_{N-i+1,j}.

Output Specification

Output the length of the largest explorable contiguous subsequence of floors.

Sample Input

5 3

Sample Output


Explanation for Sample

The largest contiguous subsequence of floors that is explorable is [3, 5].


There are no comments at the moment.