AtCoder Beginner Contest 322 E

https://atcoder.jp/contests/abc322/tasks/abc322_e

状態を各パラメータの値とします。ただし、パラメータはP以上は同じなので、そのパラメータの状態はP+1(<=6)で、パラメータ数は5以下なので、状態数は7776以下です。タプルにするとうまくいかないので、状態は整数で表します。

// Product Development
#![allow(non_snake_case)]

use std::cmp::min;


//////////////////// constants ////////////////////

const INF: i64 = 10i64.pow(18);


//////////////////// library ////////////////////

fn read<T: std::str::FromStr>() -> T {
    let mut line = String::new();
    std::io::stdin().read_line(&mut line).ok();
    line.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>().split_whitespace()
            .map(|e| e.parse().ok().unwrap()).collect()
}


//////////////////// Item ////////////////////

struct Item {
    C: i64,
    A: Vec<u32>
}

impl Item {
    fn read() -> Item {
        let v: Vec<u32> = read_vec();
        let C = v[0] as i64;
        let A: Vec<u32> = (1..v.len()).map(|i| v[i]).collect();
        Item { C, A }
    }
}


//////////////////// process ////////////////////

fn read_input() -> (u32, Vec<Item>) {
    let v = read_vec();
    let (N, P) = (v[0], v[2]);
    let items: Vec<Item> = (0..N).map(|_| Item::read()).collect();
    (P, items)
}

fn encode(S: &Vec<u32>, P: u32) -> usize {
    S.iter().rev().fold(0, |x, &y| x*(P+1)+y) as usize
}

fn decode(n: usize, K: usize, P: u32) -> Vec<u32> {
    let mut S: Vec<u32> = vec![0; K];
    let mut m: u32 = n as u32;
    for i in 0..K {
        S[i] = m % (P+1);
        m /= P+1
    }
    S
}

fn initialize_dp(K: usize, P: u32) -> Vec<i64> {
    let mut dp: Vec<i64> = vec![INF; ((P+1) as usize).pow(K as u32)];
    dp[0] = 0;
    dp
}

fn update_dp(item: &Item, dp: &Vec<i64>, P: u32) -> Vec<i64> {
    let mut new_dp: Vec<i64> = dp.to_vec();
    let K = item.A.len();
    for (k0, &n0) in dp.iter().enumerate() {
        let S0 = decode(k0, K, P);
        let S: Vec<u32> = (0..K).map(|j| min(P, S0[j]+item.A[j])).collect();
        let k = encode(&S, P);
        new_dp[k] = min(new_dp[k], n0 + item.C)
    }
    new_dp
}

fn F(P: u32, items: Vec<Item>) -> i64 {
    let K = items[0].A.len();
    let mut dp = initialize_dp(K, P);
    for item in items.into_iter() {
        dp = update_dp(&item, &dp, P)
    }
    let n = *dp.last().unwrap();
    if n == INF {
        -1
    }
    else {
        n
    }
}

fn main() {
    let (P, items) = read_input();
    println!("{}", F(P, items))
}