hello codeforces!!

Since the height of the corridor is five, the problem can be solved with a bitmask DP, where you would have as your states your current coordinate and the bitmask for the current column and the next column. You should traverse the corridor in the following manner: Place tatami at position (i, j) (if you haven't placed one beforehand) and then go to (i + 1, j). If i = 5, it means you have already completed that column and should proceed to (0, j + 1).

The bitmask would store which of the squares have already been occupied by tatamis. If your current square has already been occupied by a tatami, skip it. Otherwise, there are two ways to place it: Horizontally, occupying spots (i, j) and (i, j + 1) or Vertically, occupying (i, j) and (i + 1, j).

Say bits in positions [0, 4] will reference the current column and [5, 9] the next column. If you place a tatami horizontally, you should activate bits i and i + 5 to represent that those positions have been occupied. If you place it vertically, activate bits i and i + 1. Once your i coordinate has reached 5, the first 5 bits of the bitmask will no longer be relevant, since these such bits are a reference to the column that you have already passed by. In that case, you can do mask >>= 5 to shift the bits from [5, 9] to [0, 4].