Why Bitmasks Work

A profile for $n$ rows is a sequence of $n$ bits. Instead of storing an array of booleans, you compress this into a single integer from $0$ to $2^n - 1$.

For example, with $n = 3$, profile $5$ (binary $101$) means rows $0$ and $2$ have protruding cells, while row $1$ is clear. This lets you use $dp[col][mask]$ where $mask$ ranges over all profiles. Bitmasks make state transitions fast: you can check and modify individual bits with AND, OR, and XOR operations in constant time.