bitset解法でもう参照されない値を適宜消すことでメモリが十分削減できることを示します。
Nに対応するサンドイッチの組を右上から食べる場合を考えます。これが同じ行に \(2\) 個以上並んでいる場合、左の物を処理する前により右の物が先に処理されます。同じ列に並んでいる場合は上の物が先に処理されます。これから参照されるので消すことが出来ない物の集合を \(S\) としたとき、その任意の元について、同じ行の左側に \(S\) の元が存在しないか、同じ列の下側に \(S\) の元が存在しません。そして、このような \(S\) の要素数の最大値を \(R\) 行 \(C\) 列の場合について帰納的に考えると \(|S| \leq R+C-1\) と言えます。

他のパターンについても同じことが言え、保持する必要のあるbitsetの個数が高々 \(4(R+C-1)\) と分かります。