I write it here because there exist data sets which will TL it out.

1. Sort rows ascendingly
2. Sort ships descendingly
3. Recurse row-by-row, ship-by-ship
4. Keep ships in the linked list, so you don't have to skip them over and over once they are taken.
5. For each row try only next ships (1+2+3 is same as 1+3+2).
6. Once you reach the last row, don't recurse over it, just pick remaining ships.

This yields AC in 0.015 sec

More optimizations can be done:
1. For each row store index of the first ship which fits in it
(don't forget to skip this ship(s) if it's already taken by the time you reach the row)
2. Store amounts of same-size ships, so that 2+2 is processed only once with 6 ships of size 2, but not C(2,6) times.

Edited by author 30.07.2008 14:41

Tests in this problem are quite stupid. I've got AC with BF in 0.015! When I stored amounts of same-size ships, I've got TLE #7 many times with all kinds of optimization. Really bad problem, surely must be replaced.