Ok, I have some ideas, and my solution passes system tests in practice room, but not sure if it's correct.

The idea of my solution is that if we look at each rook as an edge between (row i) and (col j), then the graph should not have a cycle. Additionally, when we pair the rooks up, there should be at most one pair on each row and each columns.

Also, we should not introduce any new pairs of rooks. Then for each existing rook, we decide if it will be contained in a row pair, or a column pair (2^20 possibilities), and check if there is a way to make a matching without violating the above conditions.

Let's construct a graph with n red vertices and m blue vertices. For each '#' add an edge between corresponding vertices. Then we get a bipartitely colored forest. Now we want to add some edges between vertices of different colors, and satisfy the following:

1. Keep it a forest.
2. Each tree (connected component) contains odd number of vertices.
3. Root the trees in an arbitrary way. We call a node "odd" if it has odd number of descendants (including itself). There must not be a node that has three or more odd children.

The final state will look like the following. Black edges are newly added edges. Other colors represent original components.

When the final state satisfies the conditions above, black edges can be uniquely assigned to one of colored components. For example, in the previous example, edges 1, 2, 3 should be assigned to green, purple, and orange, respectively. Look at the following picture:

We want to connect node a with some blue node, node b with some red node, and node c with some red node. It doesn't really matter which red/blue nodes to choose. We just need to make sure that we don't form any cycles.

Thus, we try all subsets of vertices that have "tails" (in the example above we chose three nodes a, b, c). Check the conditions 2 and 3. For these conditions, the choice of nodes with question marks doesn't matter.

Can we satisfy the condition 1? For this, it is important to distinguish two types of components: a component with at least two nodes (it always have both red and black) and an isolated vertex. Let rneed, bneed be the number of red/blue question marks, rsingle, bsingle be the number of red/blue isolated vertices, and let comp be the number of non-isolated components. Then, it's not hard to prove that a valid assignment is possible if and only if max(rneed - rsingle, 0) + max(bneed - bsingle, 0) ≤ comp - 1.

My sad story: Medium failed on 1 test out of 280 cause it runs 2.1s (TL=2s). Get 12th place instead of 4th.

;)

Heyy! No screencast since long :(
Everything alright??

I'm sorry, looks like I accidentally send the comment, good version of the comment is below.

For k ≤ 8 we can do meet-in-the-middle, I've used Fenwick tree here, number of operations is about . For k > 8 real value of d is no more than 5·10⁷ and much smaller if k > 9, so for now I will say that k = 9 is the worst case. We will sort all the values from big to small and then do a bruteforce the following way:

void brute(int k, int pos, int sum) {
    if (D <= 0) return;
    if (k == 0) {
        D -= (int)(sum <= 0);
        return;
    };
    if (n - pos < k || getSum(pos, pos + k) < sum) return;
    brute(k - 1, pos + 1, sum - a[pos]);
    brute(k, pos + 1, sum);
}

I didn't prove it properly, but I'm pretty sure that every O(k) steps I will reduce D by 1, so the number of operations is about 5·10⁸.