LCC '23 Contest 3 S5 - Snowstorm

View as PDF

Submit solution

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

Problem types

As you know, Snow loves snow. Snow loves snow to her toes. Its shiny white glow, its gentle flow. Even though, recently there has been a lot of snow - a bit too much snow. Snow beyond her toes; snow to her knees! The cute fluffy snow, initially shallow, now a thick and slushy dough. This causes Snow a bit of woe - and to her neighborhood, too! Houses in a grid, laid row by row, all pillowed by snow, the windows overflowed, with zero airflow. The snow, meters tall, towers over, casting a looming shadow...


Snow passionately cries, as she runs into her room, crying.

From her TV, a tired weather forecaster states:

Our reports showed a massive anomaly in the forecasted snow; huge clouds crystallizing left and right, flaking and falling.

A snowstorm, bigger than any we have seen in the past 1000 years, is forming.

Currently, it's headed for the Snowdin district - residents in the area are advised to stay indoors.

Upon hearing this, Snow gasps and comes out of her room. The Snowdin district is where she and her friends live! She begins to worry about her friends and whether they will be okay.

As she quietly sniffles and wipes her tears, the forecaster elaborates:

However, this snowstorm seems to behave strangely - it will only fall on a perfectly rectangular grid of houses, although we don't know the exact dimensions of this rectangle or which houses it will cover yet.

Snow finds this rather strange, but it might be good news! The houses in the Snowdin district are arranged in a R by C grid (1 \le R \times C \le 10^6). She pulls out a map of the Snowdin district and marks her and her friends' houses as #, while other houses are marked as ..

The forecaster said that the snowstorm's rectangle would be massive, but she wonders what the maximum size is such that none of her or her friends' houses are affected. Even though knowing this will not necessarily improve the situation, it might help Snow plan for the worst-case scenario.

Please help put Snow at ease and tell her what the maximum area of the snowstorm is, such that it does not cover any houses marked as #.


Subtask 1 [30%]

1 \le R \times C \le 5 \times 10^3

Subtask 2 [70%]

1 \le R \times C \le 10^6

There is at least one #.

Input Specifications

The first line contains two integers, R and C.

The next R lines contains a string of C characters, either . or #.

Output Specification

Output one integer, representing the maximum area of snowfall such that no # are covered.

Sample Input 1

5 5

Sample Output 1



There are no comments at the moment.