\(K=1,2,\dots,\lfloor\frac{N}{2}\rfloor\) についての解を列挙することも可能です．

公式解説と同様に言い換えます．

合計 \(3N\) 個ある（ケーキ, カテゴリー）の組から、\(2K\) 個を次の条件をともにみたすように選び、対応する値の総和を最大化せよ。

• 各ケーキは高々 \(1\) 回しか選べない
• 各カテゴリーは偶数回ずつ選ばれる。

ケーキ \(l,\dots,r-1\) から \(k\) 個選ぶ方法のうち，カテゴリ毎の選んだ個数 \({}\bmod{2}\) がそれぞれ \(x,y,z\) であるようなものについての，対応する値の総和の最大値を \(g[l,r][x,y,z][k]\) とします（そのような選び方が存在しない場合は \(-\infty\) とします）． 求める値は（ケーキが 0-indexed だとして） \(g[0,N][0,0,0][2K]\) です．

\(x,y,z\) を bit 表示に対応付けて \(b\ (0\leq b<2^3)\) で表すことにすれば，以下が成り立ちます． \[g[l,r][b][k]=\max_{\substack{b_0\oplus b_1=b\\k_0+k_1=k}}\left(g[l,m][b_0][k_0]+g[m,r][b_1][k_1]\right)\]

max-plus convolution の形ではありますが，このままでは高速な計算ができません． ここで \(k<\mathrm{popcount}(b)\) または \((k-\mathrm{popcount}(b))\bmod 2\neq 0\) ならば \(g[l,r][b][k]=-\infty\) なので以下のように置き直します．

\[f[l,r][b][i]=g[l,r][b][2i+\mathrm{popcount}(b)]\]

すると \(0\leq i\leq \frac{r-l-\mathrm{popcount}(b)}{2}\) において \(f[l,r][b][i]\) は \(-\infty\) でなく，上に凸であることが確認できます． 従って上に凸な列についての max-plus convolution を用い，分割統治の要領で計算できます．

カテゴリーの種類数を \(C\)（本問題では \(C=3\)）としたとき時間計算量は monotone-minima を用いて \(O(4^CN(\log N)^2)\) 時間などとなり，高速な言語であれば通ります．

実装例(C++, 1548ms)