For each row, split the cells into maximal consecutive segments which do not contain #.

We call each segment a component.

Inside one component, if one cell is removed, then all cells in that component can also be reached by moving left and right. So we can think that each component is either completely kept or completely removed.

For every component, store its interval \([l,r]\) and its value is the number of + cells minus the number of - cells.

If a component is removed, then every component in the next row which intersects with it must also be removed, because we can move down to that component.

There are at most

\[ \left\lceil \frac{M}{2} \right\rceil \le 15 \]

components in one row, since two components must have at least one # between them.

So we can use a bitmask to represent the removed components of each row.

Let

\[ dp[i][mask] \]

be the maximum score after processing the first \(i\) rows, where mask is the set of removed components in row \(i\).

Initially,

\[ dp[0][0] = 0 \]

Suppose the previous row has state mask.

For every removed component in row \(i-1\), find all components in row \(i\) whose intervals intersect with it. These components must also be removed.

Let this set be nxtMask. Then we can update

\[ dp[i][nxtMask] = \max(dp[i][nxtMask], dp[i-1][mask]) \]

After that, every component which is not removed contributes its value to the answer.

We can also choose to remove more components in the current row.

If component \(j\) is not removed yet, we can remove it by

\[ dp[i][mask \cup {j}] = \max \left( dp[i][mask \cup {j}], dp[i][mask] - sum_{i,j} \right) \]

We process masks in increasing order, so this transition can generate every possible superset of the forced removed components.

The answer is

\[ \max_{mask} dp[N][mask] \]

If \(C\) is the maximum number of components in one row, then

\[ C \le 15 \]

and the complexity is

\[ O(NC^2 2^C) \]

My submission: AtCoder #78630211