toamさんのユーザー解説 の行間を埋めたものです。

\(\max(X_i+X_j,Y_i+Y_j,Z_i+Z_j) \leq \max(X_i,Y_i,Z_i) + \max(X_j,Y_j,Z_j)\) が成り立ちます。…(★)

この不等式において等号が成立するための必要十分条件は「\(X,Y,Z\) のどれで max を達成しているかが、 \(i\) と \(j\) で一致していること」です。

よって、「\(\max(X_i+X_j,Y_i+Y_j,Z_i+Z_j)\) の \(K\) 個の和」の上界として「\(\max(X_i,Y_i,Z_i)\) の \(2K\) 個の和」を得ます。

\(\max(X_i,Y_i,Z_i)\) が大きい方から \(2K\) 個を取ったとき、「\(X\) で max を達成しているもの」「\(Y\) で max を達成しているもの」「\(Z\) で max を達成しているもの」がそれぞれ偶数個ずつあれば、それらの中でペアを組むと、各ペアで(★)式の等号が成立し、上界を達成することができます。

そうでないとき、偶数個ずつになるように微調整します。

\(\max(X_i,Y_i,Z_i)\) が大きい方から \(2K\) 個を選ぶことで、\(N\) 個のケーキには

1. \(X_i\) を使うやつ
2. \(Y_i\) を使うやつ
3. \(Z_i\) を使うやつ
4. どれも使わないやつ

という4種類のラベルのいずれかがついた状態になります。これを基本の状態とし、ここからラベルをつけ替えることを考えます。目的は、「1,2,3のラベルがついているものがそれぞれ偶数個、かつ、1,2,3のラベルがついているものが合計で \(2K\) 個になるとき、ラベルの通りに和をとったときの最大値を求めること」です。「\(\max(X_i,Y_i,Z_i)\) が大きい方から \(2K\) 個を選ぶ」とした今のラベルの貼り方は条件を満たしていないものの和は最大となっているので、条件を満たすためにラベルをつけ替えればつけ替えるほど損をすることになります。よってラベルの個数の偶奇の条件に合うように最小限のつけ替えを考えると1,2,3の各ラベルのつけ替えは高々2個であることがわかります（詳細はtoamさんの解説へ）。

このことから
\(\mathrm{dp}[i][dx][dy][dz]\) を

• i番目までのケーキのうち
• 1のラベルがつけられたものの個数の増減がdx
• 2のラベルがつけられたものの個数の増減がdy
• 3のラベルがつけられたものの個数の増減がdz

であるときの、和の増加量の最大値

とするDPを考えます。ラベルの付け替えは高々2個であることから、i がどのような値であっても、dx,dy,dz は -2～2 の範囲のみ考えれば十分です。

最後にこのDPの結果のうち、1,2,3のラベルの個数の偶奇と1,2,3のラベルの個数の合計が条件に合うものを見れば良いです。

この問題のように「\(\max(X_i,Y_i,Z_i)\) の和の最大値」のようなものを求める問題は「\(X_i,Y_i,Z_i\) から好きなものを選ぶときの和の最大値」のように読み替えると見通しが良くなることがあります。