コンボボーナスは次のように解釈しましょう．

• 置いたブロックが直前に置いたものと同じ色であれば \(Y\) 加点．そうでなければ加点なし．

すると，色ボーナスとコンボボーナスについては，箱をひとつ置くたびに「その時点でのスコア」が計算できます．したがって，まず全色ボーナスを無視すると，次を計算していく dp により計算できます：

• \(dp[c]\)：最後に置いた箱の色が \(c\) であるとき，それまで取得したスコアとしてありうる最大値．

ここから全色ボーナスを考慮するには，dp の状態として，「今まで一度でも置いたことがある色の集合」を追加すればよいです．つまり，

• \(dp[c][s]\)：最後に置いた箱の色が \(c\) であり，これまで置いた色の集合が \(s\) であるときの，そこまでに取得した色ボーナス・コンボボーナスの最大値

としてこれを計算していけばよいです．

dp の状態は \(NM2^M\) で，各状態からの遷移は置く・置かないの 2 通りなので，全体として \(O(NM2^M)\) 時間で解くことができます．

解答例：https://atcoder.jp/contests/arc010/submissions/42177354