JOCHEF - Farmer Sepp
Chief Farmer Josef aka Sepp needs to crop hay several times through the summer. Due to high petrol costs he can currently use his truck only once to drive to a spot where he will harvest the dried grass. Lazy by nature, John does not want to harvest those parts of the field which contain cows, since this would involve too much energy. Furthermore, John just crops a rectangular part of the field.
Input
Input contains multiple test cases. You are given three integers M, N, F (0 < M, N <= 4000), (0 <= F <= 1000000) which describe the size of the field (M rows, N columns, F unit area of such a field). Then follows the actual map which consists of M lines, each line containing N times the letters 'H' or 'C' standing for "Hay" or "Cow". Input terminates with M = N = 0.
Output
Print the size of the largest field, which "Sepp" would harvest.
Example
Input: 9 10 1 CHCHHHCCCC CCHCHCHHHC CCHCHHCCCC CHHHHHCHHH CHCHHHCCCH CCCCHHHCHH HHHCCHCCCC HCHHHHCCCH CHHCCCCHHC 0 0 Output: 8
hide comments
|
~!(*(@*!@^&:
2010-06-09 18:02:09
8 = 2 x 4 x 1? (F=1); and the largest rectangle without COW is 2x4. |
|
Eternia:
2010-06-09 18:02:09
I also used the same memory as Damir and I got AC
|
|
:D:
2010-06-09 18:02:09
You can't get faster than O(M*N), unless you're not reading the whole input :) |
|
Josef Ziegler:
2010-06-09 18:02:09
@Damir You are using too much memory. |
|
Damir Ferizovic:
2010-06-09 18:02:09
Is there anything faster than O(NM) ?
|
|
|
Josef Ziegler:
2010-06-09 18:02:09
F is the unit area, since you do not know how large the rectangle in reality is |
|
|
~!(*(@*!@^&:
2010-06-09 18:02:09
the problem requires calculate the largest rectangle which contains only H? |
|
|
~!(*(@*!@^&:
2010-06-09 18:02:09
what is the role of F? |
|
|
Josef Ziegler:
2010-06-09 18:02:09
I agree that it could be misleading, however it's not wrong 8). "You are given three integers N,M,F (...) (...)" does not say anything about the order of the input, you get this information by looking at the example. I clarified the input description nonetheless. |
| Added by: | Josef Ziegler |
| Date: | 2010-04-15 |
| Time limit: | 1s |
| Source limit: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Languages: | All |
| Resource: | Josef Ziegler |
RSS