Subtask 1

The simplest solution is to consider all ~\binom{n}{r} \binom{m}{s}~ placings of lines.

Time Complexity: ~\mathcal O(\binom{n}{r} \binom{m}{s} nm)~

Subtask 2

If we fix the placing of lines going in one direction, then the optimal placing of lines going in the other direction can be computed much faster. There are two possible approaches:

• We can use binary search to find an optimal computing time. Given a candidate for an optimal computing time and placing of all horizontal lines, we can place the vertical lines from the leftmost to the rightmost one using greedy approach: each vertical line should be put as far to the right as possible. This solution runs in ~\mathcal O(\binom{n}{r} nm \log S)~ time, where ~S~ is the sum of all computation times for individual squares.

• Another approach considers all ~\binom{n}{r}~ placings of horizontal lines. For each placing, it calculates the minimal processing time using dynamic programming. Let ~min[i][j]~ be the minimal processing time of ~i~ first columns divided with ~j~ meridians. The array ~min~ can be easily filled in ~\mathcal O(m^2n)~ time. The overall running time is ~\mathcal O(\binom{n}{r}m^2n)~.

Time Complexity: ~\mathcal O(\binom{n}{r} nm \log S)~ or ~\mathcal O(\binom{n}{r}m^2n)~