Yes, it is. Let dp[i][mask] be the maximal number of passengers we can sit on the first i rows such that none of them sit close to each other and the i'th row is occupied exactly as in the mask (0 <= mask <= 63, if the j'th bit in the mask is 1, then the seat (j + 1) is occupied, otherwise it is not). Now, to compute dp[i][mask] we need to iterate through all possible masks "prev" of the (i - 1)'st row. For each such valid mask prev ("valid" means that none of the passengers on the (i - 1)'st and i'th rows sit close to each other) we have to relax our answer by dp[i][mask] = max(dp[i][mask], dp[i - 1][prev] + (the number ones in the mask)). Additionally, we can maintain the previous mask pointer[i][mask] = prev for each dp[i][mask] which gives us the best answer. When done with computing dp, we have to run through all valid masks of the last row and check whether dp[n][mask] >= k. If there is no such mask, then the answer is impossible. Otherwise, remember this mask and easily restore the answer by using those pointers to "prev" masks.

Edited by author 01.05.2020 17:30

Edited by author 01.05.2020 17:30

i also get wa10

Test helped me:

Input:
2 2
***|_|.**
**.|_|***

Output:
POBEDA
2C
1D

2 2
.**|_|***
*.*|_|***
Ans:
PORAZHENIE

One more:

Input:
1 5
...|_|...

Output:
PORAZHENIE