12795 - Ecology

[nada_elnokaly]

do any one have an idea how can we solve this problem within the time limit !?

[brianfry713]

My code gets AC in 57 seconds.

I first precalculate all possible shapes and their sizes for 1 <= M <= 10. For M = 10 there are 36,446 shapes. That takes less than a second on my machine. I use a struct with a set<pair<int, int> > of points and the height and width of the shape.
I then start reading the input and test each shape on each location it fits.

[LCSFC]

Please help me with this problem. Are you sure there is only about 36000 shapes for M=10? I wanna test my algorithm, it gives 4900 shapes for M=2, 14404 shapes for M=3...is that right?

[brianfry713]

M, Unique shapes
1, 1
2, 2
3, 6
4, 19
5, 63
6, 216
7, 760
8, 2725
9, 9910
10, 36446

[LCSFC]

Thank you very much! With your results i could find my mistakes and solve it. Thanks!