BearPaints | Topcoder Archive

Problem Statement

Limak is a little polar bear. Today he found two things in the snow: a bucket of blue paint and a white rectangular grid with W times H square cells.

Limak is going to paint some (possibly even all) cells blue. He wants to do it in such a way that the blue cells will form a completely filled blue rectangle. He has enough paint for M cells. What is the largest possible area of a blue rectangle he can paint?

Definition

Class:: BearPaints
Method:: maxArea
Parameters:: int, int, long
Returns:: long
Method signature:: long maxArea(int W, int H, long M)
(be sure your method is public)

Constraints

W and H will be between 1 and 10^6, inclusive.
M will be between 1 and 10^12, inclusive.

Examples

```
3
```
```
5
```
```
14
```
```
Returns: 12
```
Limak has a grid that is W = 3 cells wide and H = 5 cells tall. He doesn't have enough paint to color all 15 cells. He also cannot color just 14 or 13 cells in a way that would produce a blue rectangle. The best he can do is to color four consecutive rows blue. This will produce a blue rectangle. Its area is 12 squares.
```
4
```
```
4
```
```
10
```
```
Returns: 9
```
Here the best solution is to paint a rectangle of size 3 times 3 blue. (A square is a valid rectangle.)
```
1000000
```
```
12345
```
```
1000000000000
```
```
Returns: 12345000000
```
Limak has more than enough paint to make whole grid blue.
```
1000000
```
```
1000000
```
```
720000000007
```
```
Returns: 720000000000
```
Limak's grid is a square with side 10^6. Limak can paint a rectangle of size 800,000 times 900,000.

999999999999

Returns: 999999000000

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.