G - Patisserie ABC 3
Source: atcoder
Difficulty: 625

Problem Statement
Takahashi, a patissier working at the ABC pastry shop, decided to sell assorted cakes to commemorate AtCoder Beginner Contest 400.
The shop sells
N
kinds of cakes: cake
1
, cake
2
,
\ldots
, cake
N
.
Each cake has three non-negative integer values: beauty, tastiness, and popularity. Specifically, cake
i
has beauty
X_i
, tastiness
Y_i
, and popularity
Z_i
.
He considers pairing up these cakes into
K
pairs without overlaps.
Formally, he will choose
2K
distinct
integers
a_1,b_1,a_2,b_2,\ldots,a_K,b_K
between
1
and
N
(inclusive), and pair cake
a_i
with cake
b_i
.
The price of a pair formed by cakes
a_i
and
b_i
is
\max(X_{a_i} + X_{b_i},\, Y_{a_i} + Y_{b_i},\, Z_{a_i} + Z_{b_i})
.
Here,
\max(P,Q,R)
denotes the greatest value among
P,Q,R
.
Find the maximum possible total price of the
K
pairs.
You are given
T
test cases; solve each of them.
Constraints
1\leq T\leq 1000
2\leq N \leq 10^5
The sum of
N
over all test cases in each input file is at most
10^5
.
1\leq K \leq \lfloor \frac{N}{2}\rfloor
(For a real number
x
,
\lfloor x\rfloor
denotes the greatest integer not exceeding
x
.)
0\leq X_i,Y_i,Z_i \leq 10^9
All input values are integers.
Input
The input is given from Standard Input in the following format:
T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T
\mathrm{case}_i
represents the
i
-th test case. Each test case is given in the following format:
N
K
X_1
Y_1
Z_1
X_2
Y_2
Z_2
\vdots
X_N
Y_N
Z_N
Output
Print
T
lines. The
i
-th line
(1\leq i\leq T)
should contain the answer to the
i
-th test case.
Sample Input 1
1
3 1
6 3 8
3 5 0
2 7 3
Sample Output 1
12
We form one pair out of three cakes.
If we pair cake
1
with cake
2
, the price is
\max(6+3,\,3+5,\,8+0) = 9
.
If we pair cake
1
with cake
3
, the price is
\max(6+2,\,3+7,\,8+3) = 11
.
If we pair cake
2
with cake
3
, the price is
\max(3+2,\,5+7,\,0+3) = 12
.
Hence, pairing cake
2
with cake
3
gives the highest price, which is 12.
Sample Input 2
2
5 2
1 2 3
1 2 3
1 2 3
1 2 3
100 100 200
6 2
21 74 25
44 71 80
46 28 96
1 74 24
81 83 16
55 31 1
Sample Output 2
209
333
Note that each cake can appear in at most one pair.
Also note that there can be different cakes with identical values of beauty, tastiness, and popularity.
For the first test case, pairing cake
1
with cake
2
gives a price of
6
, pairing cake
3
with cake
5
gives a price of
203
, and choosing these two pairs yields a total price of
209
, which is the maximum.
For the second test case, pairing cake
2
with cake
3
gives a price of
176
, pairing cake
4
with cake
5
gives a price of
157
, and choosing these two pairs yields a total price of
333
, which is the maximum.

C++ solution:
// Author: YE Minghan
#include<bits/stdc++.h>
using namespace std;
#ifdef DEBUG
#include "templates/debug.h"
#else
#define dbg(...) (void)0
#define here (void)0
#endif
#define ll long long
#define endl '\n'
#define PB emplace_back
#define PPB pop_back
#define MP make_pair
#define ALL(Name) Name.begin(),Name.end()
#define PII pair<int,int>
#define VI vector<int>
#define GI greater<int>
#define fi first
#define se second

const int N=100005;
int n,k;
array<int,3>a[N];
ll dp[N][12];
void ck(ll &x,ll y){x=max(x,y);}

int main()
{
	ios::sync_with_stdio(false),cin.tie(nullptr);
	int _;cin>>_;while(_--)
{
	cin>>n>>k;
	for(int i=1;i<=n;i++)
		for(int j=0;j<3;j++)cin>>a[i][j];
	sort(a+1,a+n+1,[](auto x,auto y){return max({x[0],x[1],x[2]})>max({y[0],y[1],y[2]});});
	memset(dp,0xc0,8*12*(n+3));
	dp[0][0]=dp[n+1][0]=0;
	for(int i=1;i<=k<<1;i++)
		for(int j=0;j<12;j++)
		{
			ck(dp[i][j],dp[i-1][j]+a[i][0]);
			ck(dp[i][j^1],dp[i-1][j]+a[i][1]);
			ck(dp[i][j^2],dp[i-1][j]+a[i][2]);
			if(j<8)ck(dp[i][j+4],dp[i-1][j]);
		}
	for(int i=n;i>k<<1;i--)
		for(int j=0;j<12;j++)
		{
			if(j<8)ck(dp[i][j+4],dp[i+1][j]+a[i][0]);
			if(j<8)ck(dp[i][(j+4)^1],dp[i+1][j]+a[i][1]);
			if(j<8)ck(dp[i][(j+4)^2],dp[i+1][j]+a[i][2]);
			ck(dp[i][j],dp[i+1][j]);
		}
	ll ans=0;
	for(int i=0;i<12;i++)ck(ans,dp[k<<1][i]+dp[(k<<1)+1][i]),dbg(i,ans);
	cout<<ans<<endl;

}

	return 0;
}

Go solution:
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
	"strings"
)

type Pair struct {
	first  int64
	second int64
}

func solve(n, k int, cakes [][3]int64, c int64) Pair {
	dp := make([]Pair, 8)
	for i := range dp {
		dp[i] = Pair{-1 << 60, 0}
	}
	dp[0] = Pair{0, 0}
	for i := 0; i < n; i++ {
		dp2 := make([]Pair, 8)
		copy(dp2, dp)
		for mask := 0; mask < 8; mask++ {
			for bit := 0; bit < 3; bit++ {
				newMask := mask ^ (1 << bit)
				addedVal := 2*cakes[i][bit] - c
				newVal := dp[mask].first + addedVal
				newCnt := dp[mask].second + 1
				if newVal > dp2[newMask].first || (newVal == dp2[newMask].first && newCnt > dp2[newMask].second) {
					dp2[newMask] = Pair{newVal, newCnt}
				}
			}
		}
		dp = dp2
	}
	return dp[0]
}

func solveCase(n, k int, cakes [][3]int64) int64 {
	left, right := int64(0), int64(1<<31)
	for left+1 < right {
		mid := (left + right) / 2
		res := solve(n, k, cakes, mid)
		if res.second >= 2*int64(k) {
			left = mid
		} else {
			right = mid
		}
	}
	res := solve(n, k, cakes, left)
	return (res.first + 2*int64(k)*left) / 2
}

func main() {
	scanner := bufio.NewScanner(os.Stdin)
	scanner.Scan()
	t, _ := strconv.Atoi(scanner.Text())
	for i := 0; i < t; i++ {
		scanner.Scan()
		nk := strings.Fields(scanner.Text())
		n, _ := strconv.Atoi(nk[0])
		k, _ := strconv.Atoi(nk[1])
		cakes := make([][3]int64, n)
		for j := 0; j < n; j++ {
			scanner.Scan()
			xyz := strings.Fields(scanner.Text())
			x, _ := strconv.ParseInt(xyz[0], 10, 64)
			y, _ := strconv.ParseInt(xyz[1], 10, 64)
			z, _ := strconv.ParseInt(xyz[2], 10, 64)
			cakes[j] = [3]int64{x, y, z}
		}
		fmt.Println(solveCase(n, k, cakes))
	}
}

Java solution:
import java.io.*;
import java.util.*;

public class Main {
    static final int MAX_N = 1 << 17;
    static int N, K;
    static int[] X = new int[MAX_N];
    static int[] Y = new int[MAX_N];
    static int[] Z = new int[MAX_N];
    static Integer[] idx = new Integer[MAX_N];
    static long[][][] dp = new long[2][4][1 << 3];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter pw = new PrintWriter(System.out);
        StringTokenizer st = new StringTokenizer(br.readLine());
        int T = Integer.parseInt(st.nextToken());

        while (T-- > 0) {
            st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken());
            K = Integer.parseInt(st.nextToken());
            for (int i = 0; i < N; i++) {
                st = new StringTokenizer(br.readLine());
                X[i] = Integer.parseInt(st.nextToken());
                Y[i] = Integer.parseInt(st.nextToken());
                Z[i] = Integer.parseInt(st.nextToken());
                idx[i] = i;
            }

            Arrays.sort(idx, 0, N, (l, r) -> {
                long maxL = Math.max(X[l], Math.max(Y[l], Z[l]));
                long maxR = Math.max(X[r], Math.max(Y[r], Z[r]));
                return Long.compare(maxR, maxL);
            });

            int now = 0;
            for (int c = 0; c <= 3; c++) {
                for (int i = 0; i < (1 << 3); i++) {
                    dp[now][c][i] = (long) -1e18;
                }
            }
            dp[now][0][0] = 0;

            for (int i = 0; i < N; i++) {
                int nxt = 1 - now;
                for (int c = 0; c <= 3; c++) {
                    for (int k = 0; k < (1 << 3); k++) {
                        dp[nxt][c][k] = (long) -1e18;
                    }
                }
                for (int c = 0; c <= 3; c++) {
                    for (int k = 0; k < (1 << 3); k++) {
                        // Skip current cake
                        int nc = c;
                        if (i < K + K) nc++;
                        if (nc <= 3) {
                            dp[nxt][nc][k] = Math.max(dp[nxt][nc][k], dp[now][c][k]);
                        }
                        // Use current cake
                        int[] V = {X[idx[i]], Y[idx[i]], Z[idx[i]]};
                        for (int t = 0; t < 3; t++) {
                            int nk = k ^ (1 << t);
                            nc = c;
                            if (i >= K + K) nc--;
                            if (nc >= 0) {
                                dp[nxt][nc][nk] = Math.max(dp[nxt][nc][nk], dp[now][c][k] + V[t]);
                            }
                        }
                    }
                }
                now = nxt;
            }
            pw.println(dp[now][0][0]);
        }
        pw.flush();
        pw.close();
    }
}

JavaScript solution:
const { PriorityQueue } = require('datastructures-js');

function solve() {
    const input = require('fs').readFileSync(0, 'utf-8').split('\n');
    let ptr = 0;
    const T = parseInt(input[ptr++], 10);
    for (let _ = 0; _ < T; _++) {
        const [N, K] = input[ptr++].split(' ').map(Number);
        const cakes = [];
        for (let i = 0; i < N; i++) {
            const [X, Y, Z] = input[ptr++].split(' ').map(Number);
            cakes.push([Math.max(X, Y, Z), X, Y, Z]);
        }
        cakes.sort((a, b) => b[0] - a[0]);
        const INF = 1 << 60;
        let dp = Array.from({ length: 3 }, () => Array(8).fill(-INF));
        dp[0][0] = 0;
        for (let i = 0; i < 2 * K; i++) {
            const [_, x, y, z] = cakes[i];
            const ndp = Array.from({ length: 3 }, () => Array(8).fill(-INF));
            for (let key = 0; key < 8; key++) {
                for (let j = 0; j < 3; j++) {
                    if (dp[j][key] === -INF) continue;
                    const newKey1 = key ^ 0b001;
                    ndp[j][newKey1] = Math.max(ndp[j][newKey1], dp[j][key] + x);
                    const newKey2 = key ^ 0b010;
                    ndp[j][newKey2] = Math.max(ndp[j][newKey2], dp[j][key] + y);
                    const newKey3 = key ^ 0b100;
                    ndp[j][newKey3] = Math.max(ndp[j][newKey3], dp[j][key] + z);
                }
            }
            for (let key = 0; key < 8; key++) {
                for (let j = 0; j < 2; j++) {
                    if (dp[j][key] === -INF) continue;
                    ndp[j + 1][key] = Math.max(ndp[j + 1][key], dp[j][key]);
                }
            }
            dp = ndp;
        }
        let ans = dp[0][0];
        if (N === 2 * K) {
            console.log(ans);
            continue;
        }
        const sub = Array.from({ length: 3 }, () => [-1, -1]);
        for (let i = 2 * K; i < N; i++) {
            for (let j = 0; j < 3; j++) {
                const val = cakes[i][j + 1];
                if (sub[j][0] === -1 || val > cakes[sub[j][0]][j + 1]) {
                    sub[j][1] = sub[j][0];
                    sub[j][0] = i;
                } else if (sub[j][1] === -1 || val > cakes[sub[j][1]][j + 1]) {
                    sub[j][1] = i;
                }
            }
        }
        ans = Math.max(
            ans,
            dp[1][0b001] + (sub[0][0] !== -1 ? cakes[sub[0][0]][1] : -INF),
            dp[1][0b010] + (sub[1][0] !== -1 ? cakes[sub[1][0]][2] : -INF),
            dp[1][0b100] + (sub[2][0] !== -1 ? cakes[sub[2][0]][3] : -INF)
        );
        if (N === 2 * K + 1) {
            console.log(ans);
            continue;
        }
        function getXY(x, y) {
            if (sub[x][0] !== sub[y][0]) {
                return cakes[sub[x][0]][x + 1] + cakes[sub[y][0]][y + 1];
            }
            let res = -INF;
            if (sub[x][1] !== -1) {
                res = Math.max(res, cakes[sub[x][1]][x + 1] + cakes[sub[y][0]][y + 1]);
            }
            if (sub[y][1] !== -1) {
                res = Math.max(res, cakes[sub[x][0]][x + 1] + cakes[sub[y][1]][y + 1]);
            }
            return res;
        }
        ans = Math.max(
            ans,
            dp[2][0b011] + getXY(0, 1),
            dp[2][0b101] + getXY(0, 2),
            dp[2][0b110] + getXY(1, 2),
            dp[2][0b000] + Math.max(
                ...(sub[0][1] !== -1 ? [cakes[sub[0][0]][1] + cakes[sub[0][1]][1]] : [-INF]),
                ...(sub[1][1] !== -1 ? [cakes[sub[1][0]][2] + cakes[sub[1][1]][2]] : [-INF]),
                ...(sub[2][1] !== -1 ? [cakes[sub[2][0]][3] + cakes[sub[2][1]][3]] : [-INF])
            )
        );
        console.log(ans);
    }
}

solve();

Python solution:
import sys
import threading

def main():
    import sys
    input = sys.stdin.readline
    NEG = -10**30

    T = int(input())
    for _ in range(T):
        N, K = map(int, input().split())
        cakes = [tuple(map(int, input().split())) for _ in range(N)]
        # sort indices by their max attribute descending
        idx = list(range(N))
        idx.sort(key=lambda i: max(cakes[i]), reverse=True)
        P = idx[:2*K]
        Q = idx[2*K:]

        # Prefix DP over P: how many we skip (t=0..2) and parity of X and Y picks
        dp_P = [[[NEG]*2 for _ in range(2)] for __ in range(3)]
        dp_P[0][0][0] = 0
        for i in P:
            X, Y, Z = cakes[i]
            dp2 = [[[NEG]*2 for _ in range(2)] for __ in range(3)]
            for t in range(3):
                for px in range(2):
                    for py in range(2):
                        cur = dp_P[t][px][py]
                        if cur < 0: continue
                        # skip this cake
                        if t < 2:
                            dp2[t+1][px][py] = max(dp2[t+1][px][py], cur)
                        # pick X
                        dp2[t][px^1][py] = max(dp2[t][px^1][py], cur + X)
                        # pick Y
                        dp2[t][px][py^1] = max(dp2[t][px][py^1], cur + Y)
                        # pick Z
                        dp2[t][px][py] = max(dp2[t][px][py], cur + Z)
            dp_P = dp2

        # Suffix DP over Q: how many we pick (j=0..2) and parity of X and Y
        dp_Q = [[[NEG]*2 for _ in range(2)] for __ in range(3)]
        dp_Q[0][0][0] = 0
        for i in Q:
            X, Y, Z = cakes[i]
            dp2 = [[[NEG]*2 for _ in range(2)] for __ in range(3)]
            for j in range(3):
                for px in range(2):
                    for py in range(2):
                        cur = dp_Q[j][px][py]
                        if cur < 0: continue
                        # skip
                        dp2[j][px][py] = max(dp2[j][px][py], cur)
                        # pick this cake if j<2
                        if j < 2:
                            dp2[j+1][px^1][py] = max(dp2[j+1][px^1][py], cur + X)
                            dp2[j+1][px][py^1] = max(dp2[j+1][px][py^1], cur + Y)
                            dp2[j+1][px][py]   = max(dp2[j+1][px][py],   cur + Z)
            dp_Q = dp2

        # Combine: for each t skips in P and t picks in Q,
        # match any parity (px,py) so that overall each dimension is even.
        ans = 0
        for t in range(3):
            for px in range(2):
                for py in range(2):
                    v1 = dp_P[t][px][py]
                    v2 = dp_Q[t][px][py]
                    if v1 >= 0 and v2 >= 0:
                        ans = max(ans, v1 + v2)

        print(ans)

if __name__ == "__main__":
    threading.Thread(target=main).start()

Ruby solution:
def solve_cake_pairs
  input = $stdin
  neg_value = -10**30

  test_cases = input.gets.to_i
  test_cases.times do
    # Read input for current test case
    n, k = input.gets.split.map(&:to_i)
    cakes = []
    n.times { cakes << input.gets.split.map(&:to_i) }

    # Sort indices by max attribute descending
    indices = (0...n).to_a.sort_by { |i| -cakes[i].max }

    # Split into top 2k and remaining cakes
    top = indices.take(2 * k)
    remaining = indices.drop(2 * k)

    # DP for top cakes: tracks skips (0-2) and parity of X/Y
    dp_top = Array.new(3) { Array.new(2) { Array.new(2, neg_value) } }
    dp_top[0][0][0] = 0

    top.each do |i|
      x, y, z = cakes[i]
      new_dp = Array.new(3) { Array.new(2) { Array.new(2, neg_value) } }

      (0..2).each do |skips|
        (0..1).each do |px|
          (0..1).each do |py|
            current = dp_top[skips][px][py]
            next if current == neg_value

            # Option 1: Skip (if we haven't skipped 2 already)
            if skips < 2
              new_dp[skips + 1][px][py] = [new_dp[skips + 1][px][py], current].max
            end

            # Option 2: Pick X
            new_dp[skips][px ^ 1][py] = [new_dp[skips][px ^ 1][py], current + x].max

            # Option 3: Pick Y
            new_dp[skips][px][py ^ 1] = [new_dp[skips][px][py ^ 1], current + y].max

            # Option 4: Pick Z
            new_dp[skips][px][py] = [new_dp[skips][px][py], current + z].max
          end
        end
      end

      dp_top = new_dp
    end

    # DP for remaining cakes: tracks picks (0-2) and parity
    dp_remain = Array.new(3) { Array.new(2) { Array.new(2, neg_value) } }
    dp_remain[0][0][0] = 0

    remaining.each do |i|
      x, y, z = cakes[i]
      new_dp = Array.new(3) { Array.new(2) { Array.new(2, neg_value) } }

      (0..2).each do |picks|
        (0..1).each do |px|
          (0..1).each do |py|
            current = dp_remain[picks][px][py]
            next if current == neg_value

            # Option 1: Skip
            new_dp[picks][px][py] = [new_dp[picks][px][py], current].max

            # Option 2: Pick (if we haven't picked 2 already)
            if picks < 2
              new_dp[picks + 1][px ^ 1][py] = [new_dp[picks + 1][px ^ 1][py], current + x].max
              new_dp[picks + 1][px][py ^ 1] = [new_dp[picks + 1][px][py ^ 1], current + y].max
              new_dp[picks + 1][px][py] = [new_dp[picks + 1][px][py], current + z].max
            end
          end
        end
      end

      dp_remain = new_dp
    end

    # Combine results
    max_total = 0
    (0..2).each do |t|
      (0..1).each do |px|
        (0..1).each do |py|
          top_val = dp_top[t][px][py]
          remain_val = dp_remain[t][px][py]
          if top_val != neg_value && remain_val != neg_value
            max_total = [max_total, top_val + remain_val].max
          end
        end
      end
    end

    puts max_total
  end
end

solve_cake_pairs