Subtask 1

For subtask 1, note that there are ~2^{N-1}~ ways of choosing which horizontal cuts to make, and ~2^{M-1}~ ways of choosing which vertical cuts to make. We can check all ~2^{N+M-2}~ ways of cutting in ~\mathcal{O}(NM)~ time each and output the maximum answer.

Time complexity: ~\mathcal{O}(2^{N+M-2}NM)~

Subtask 2

For subtask 2, we can still afford to brute-force all ~2^{N-1}~ ways of choosing which horizontal cuts to make, but we need a better method to find the maximum possible answer given some arrangement of horizontal cuts. We can actually do this greedily: There are two options for which cells in some column we get to keep, and we should always take the option with a higher value. However, we need to be careful with the case when there are no horizontal cuts to make sure we don't consider the possibility of making no cuts. This allows for checking some arrangement of horizontal cuts in ~\mathcal{O}(NM)~ time each.

Time complexity: ~\mathcal{O}(2^{N-1}NM)~

Subtasks 3, 4, 5

Instead of assigning colours after we made the cuts, let's consider the problem from a different perspective, where we add in the cuts one by one in some order and change the colouring after each time we add a cut. Starting from a grid where we keep all of the cells, we can notice that adding a cut corresponds to flipping the state of all cells in a half-plane from "kept" to "not kept". From this, we can notice that the set of all colourings obtainable through such flippings is equivalent to the set of all colourings obtainable through repeatedly flipping the state of all cells in some row or column. This version is much easier to work with.

Consider assigning a boolean variable ~r_i~ to each row and a variable ~c_j~ to each column, representing whether we should flip this row/column. We can keep a cell with value ~v_{ij}~ if and only if ~r_i~ and ~c_j~ are the same. Conversely, we don't get to keep the cell if and only if ~r_i~ and ~c_j~ are different. Now consider a complete weighted bipartite graph where the nodes on the left side correspond to rows and the nodes on the right side correspond to columns, and the weights are equal to the corresponding ~v_{ij}~. We can see that the problem reduces to a global min-cut problem: indeed, the set of ~r_i~ or ~c_j~ that are ~0~ correspond to one side of a cut, the set of ~r_i~ or ~c_j~ that are ~1~ correspond to the other side of the cut, and the cells we don't get to keep correspond to edges that need to be cut to separate the sets.

We can now obtain polynomial-time algorithms for the remaining subtasks:

• For subtask 3, we can consider all pairs ~(s,t)~ for some fixed ~s~ and run a max-flow algorithm like Edmonds-Karp to find the minimum weighted ~st~-cut, and take the minimum of all of these to find the global min-cut. Edmonds-Karp takes ~\mathcal{O}(VE^2)~ time on a graph with ~V~ nodes and ~E~ edges, which is ~\mathcal{O}((N+M)(NM)^2)~ in our case, and since we need to run it ~N+M~ times we get a time complexity of ~\mathcal{O}((NM(N+M))^2)~ overall. In practice, flow algorithms like Edmonds-Karp run much faster in practice and this passes subtask 3.
• For subtask 4, we can speed up the above solution by using a faster flow algorithm such as Dinic's or Push-Relabel. Dinic's algorithm gives a time complexity of ~\mathcal{O}((N+M)^5)~ and Push-Relabel gives a time complexity of ~\mathcal{O}((N+M)^4)~, both of which can pass subtask 4 if well-implemented since they run fast in practice. Alternatively, a slower algorithm designed specifically for the global min-cut problem such as the randomized Karger's algorithm can be used.
• For subtask 5, we can use the Stoer-Wagner algorithm, which runs in ~\mathcal{O}((N+M)^3)~ time.