I use two algorithms inside one program: First I try to arrange ships using heuristics with randomization. If it fails for many times (say, 1000 times) I use bruteforce with optimizations (just like many people)
I found a big numbers of different bruteforces and heuristics for this problem. I have tests for all that methods. You need just one good combination! My program works well on all tests, I've already checked more than 30 billions random tests.
A little hint: my bruteforce gets TLE 22, heuristics gets TLE 17. Good luck!
It is required to inspect all the current solutions thoroughly to decide whether all of them have some "tweaking" for specific tests or not. If any of them is universal (i.e. actually not depends on any seed or magic number), then time limit can be even capped on that. If not, then it is reasonable to increase TL somehow.