hash_dot.cpp

int mat[N][N], colSum[N], n, m, x, y, dp[N][N][2];

int go(int id, int cx, int prev) {
	if(cx > y)
		return inf;
	if(id > m)
		return (cx >= x and cx <= y ? 0 : inf);

	int& ans = dp[id][cx][prev];
	if(~ans)
		return ans;

	int dots = n - colSum[id];
	int hashes = colSum[id];
	int make_dot = inf, make_hash = inf;

	if(prev == 0) {				//prev column was dot
		make_dot = hashes + go(id + 1, cx + 1, 0);
		if(cx >= x and cx <= y)
			make_hash = dots + go(id + 1, 1, 1);
	}
	if(prev == 1) {				//prev column was hashes
		make_hash = min(make_hash, dots + go(id + 1, cx + 1, 1));
		if(cx >= x and cx <= y)
			make_dot = min(make_dot, hashes + go(id + 1, 1, 0));
	}

	return ans = min(make_hash, make_dot);
}