题解：AT_abc400_g [ABC400G] Patisserie ABC 3

JackieLiang · 2025-05-11 23:29:17 · 题解

fastest:(rust)

use itertools::*;
use memoise::*;
use proconio::marker::*;
use proconio::*;
use std::collections::*;
use superslice::Ext;

type Map<K, V> = BTreeMap<K, V>;
type Set<T> = BTreeSet<T>;
type Deque<T> = VecDeque<T>;

const MOD: u64 = 998_244_353;
const INF: i64 = 1 << 50;

fn main() {
    input! {
        t: usize,
    }

    for _ in 0..t {
        input! {
            n: usize,
            k: usize,
            mut xyz: [(i64, i64, i64); n],
        }

        xyz.sort_unstable_by_key(|(x, y, z)| *x.max(y).max(z));
        xyz.reverse();

        // dp[i][t][b]: [0, i) のなかでスルーしたのが t 個で現在の選択の偶奇状況が b
        // であるようなものの最大値
        let mut dp = [[-INF; 8]; 3];
        dp[0][0] = 0;

        for &(x, y, z) in xyz[..2 * k].iter() {
            let mut ep = [[-INF; 8]; 3];
            // x として選択する。
            for t in 0..=2 {
                for b in 0..8 {
                    ep[t][b ^ 1] = ep[t][b ^ 1].max(dp[t][b] + x);
                }
            }
            // y として選択する。
            for t in 0..=2 {
                for b in 0..8 {
                    ep[t][b ^ 2] = ep[t][b ^ 2].max(dp[t][b] + y);
                }
            }
            // z として選択する。
            for t in 0..=2 {
                for b in 0..8 {
                    ep[t][b ^ 4] = ep[t][b ^ 4].max(dp[t][b] + z);
                }
            }
            // 何も選択せずにスルーする。
            for t in 0..2 {
                for b in 0..8 {
                    ep[t + 1][b] = ep[t + 1][b].max(dp[t][b]);
                }
            }

            dp = ep;
        }

        for &(x, y, z) in xyz[2 * k..].iter() {
            let mut ep = [[-INF; 8]; 3];
            // 何も選択せずにスルーする。
            for t in 0..=2 {
                for b in 0..8 {
                    ep[t][b] = ep[t][b].max(dp[t][b]);
                }
            }
            // x として選択する。
            for t in 1..=2 {
                for b in 0..8 {
                    ep[t - 1][b ^ 1] = ep[t - 1][b ^ 1].max(dp[t][b] + x);
                }
            }
            // y として選択する。
            for t in 1..=2 {
                for b in 0..8 {
                    ep[t - 1][b ^ 2] = ep[t - 1][b ^ 2].max(dp[t][b] + y);
                }
            }
            // z として選択する。
            for t in 1..=2 {
                for b in 0..8 {
                    ep[t - 1][b ^ 4] = ep[t - 1][b ^ 4].max(dp[t][b] + z);
                }
            }

            dp = ep;
        }

        println!("{}", dp[0][0]);
    }
}

shortest(c++):

#include <bits/stdc++.h>
using namespace std;
#define pll pair<long long,long long>
#define rep(i,n) for(int i=0;i<n;++i)
long long n,k;
long long x[100000][3];
pll solve(int c){
    vector<pll> dp(8,{-((long long)1e18),0LL});
    dp[0]={0LL,0LL};
    rep(i,n){
        vector<pll> dp2=dp;
        rep(j,8){
            rep(k,3){
                pll tmp={dp[j].first+2*x[i][k]-c,dp[j].second+1};
                dp2[j^(1<<k)]=max(dp2[j^(1<<k)],tmp);
            }
        }
        dp=dp2;
    }
    return dp[0];
}
signed main(){
    int t;
    cin>>t; 
    rep(_,t){
        cin>>n>>k;
        rep(i,n) cin>>x[i][0]>>x[i][1]>>x[i][2];
        long long l=0,r=1LL<<31;
        while((l+1)<r){
            long long m=(l+r)/2;
            if (solve(m).second>=(2*k)) l=m;
            else r=m;
        }
        long long ans=(solve(l).first+2*k*l)/2;
        cout<<ans<<endl;
    }
}