FSEATS  Finding Seats
A group of K friends is going to see a movie. However, they are too late to get good tickets, so they are looking for a good way to sit all nearby. Since they are all science students, they decided to come up with an optimization problem instead of going on with informal arguments to decide which tickets to buy.
The movie theater has R rows of C seats each, and they can see a map with the currently available seats marked. They decided that seating close to each other is all that matters, even if that means seating in the front row where the screen is so big it’s impossible to see it all at once. In order to have a formal criteria, they thought they would buy seats in order to minimize the extension of their group.
The extension is defined as the area of the smallest rectangle with sides parallel to the seats that contains all bought seats. The area of a rectangle is the number of seats contained in it. They’ve taken out a laptop and pointed at you to help them find those desired seats.
Input
Each test case will consist on several lines. The first line will contain three positive integers R, C and K as explained above (1 <= R,C <= 300, 1 <= K <= R × C). The next R lines will contain exactly C characters each. The jth character of the ith line will be ‘X’ if the jth seat on the ith row is taken or ‘.’ if it is available. There will always be at least K available seats in total.
Input is terminated with R = C = K = 0.
Output
For each test case, output a single line containing the minimum extension the group can have.
Example
Input: 3 5 5 ...XX .X.XX XX... 5 6 6 ..X.X. .XXX.. .XX.X. .XXX.X .XX.XX 0 0 0 Output: 6 9
hide comments
be1035016:
20190202 17:31:27
nice problem 

farhad chowdhury:
20160419 22:54:43
phew finally after this optimization i got AC


gogo40 :
20151116 15:53:58
There are a O(R^2) solution... You can try to solve this problem firstly: http://www.spoj.com/problems/HISTOGRA/ 

Petar Bosnjak:
20150209 14:36:15
Time limit is too strict...


sasha sami:
20140725 20:45:21
O(R*R*C) can pass with some optimization


Alex Abbas:
20131227 22:22:06
The time limit is unbelievable i tried


LeBron:
20131030 09:26:31
O(R*C*C) works fine. 

Vlade087:
20111027 13:11:28
The time limit is very strict O(R*C*C) no run in time!!!!!!!!!!!! 

chetan bademi:
20100607 06:10:21
Does O(R*R*C) pass? 
Added by:  Camilo Andrés Varela León 
Date:  20071202 
Time limit:  0.209s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ERL JSRHINO NODEJS PERL6 VB.NET 
Resource:  The 2007 ACM South American Programming Contest 