AtCoder Beginner Contest 402 F

https://atcoder.jp/contests/abc402/tasks/abc402_f

左上と右下を分けて考えます。入力例2で考えると、左上から7 5 3の対角線上までの経路を考えると、[137], [135, 125], [123]です。あとで100掛けるので、[13700], [13500, 12500], [12300]となります。対角線上から右下の経路を考えると、[712], [512, 582], [382]となります。対角線上の同じマス同士で左下と右下の足したときの最大値を考えます。そのときにMで剰余を取って昇順と降順にします。そうするとMを超えないように尺取り法を使うと速く最大値を求めることができます。

// Path to Integer
#![allow(non_snake_case)]


//////////////////// 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()
}

fn pow(n: i64, e: usize, d: i64) -> i64 {
    if e == 0 {
        1
    }
    else if e == 1 {
        n
    }
    else if e % 2 == 1 {
        n * pow(n, e-1, d) % d
    }
    else {
        let m = pow(n, e/2, d);
        m * m % d
    }
}


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

type Matrix = Vec<Vec<i64>>;

fn read_matrix(N: usize) -> Matrix {
    (0..N).map(|_| read_vec::<i64>()).collect::<Vec<_>>()
}

fn read_input() -> (i64, Matrix) {
    let v: Vec<usize> = read_vec();
    let (N, M) = (v[0], v[1] as i64);
    let A = read_matrix(N);
    (M, A)
}

fn upper_left(M: i64, A: &Matrix) -> Vec<Vec<i64>> {
    let N = A.len();
    let mut v: Vec<Vec<i64>> = vec![vec![A[0][0]]];
    for i in 1..N {
        let mut w: Vec<Vec<i64>> = vec![vec![]; i+1];
        for j in 0..i {
            for n in v[j].iter() {
                w[j].push((n * 10 + A[i-j][j]) % M);        // 下へ
                w[j+1].push((n * 10 + A[i-j-1][j+1]) % M);  // 右へ
            }
        }
        v = w
    }
    let p = pow(10, N - 1, M);
    v.iter().map(|a| a.iter().map(|n| n*p%M).collect::<Vec<_>>()).
                                                        collect::<Vec<_>>()
}

fn lower_right(M: i64, A: &Matrix) -> Vec<Vec<i64>> {
    let N = A.len();
    let mut v: Vec<Vec<i64>> = vec![vec![0]];
    for i in 1..N {
        let mut w: Vec<Vec<i64>> = vec![vec![]; i+1];
        let p = 10i64.pow(i as u32 - 1);
        for j in 0..i {
            for &n in v[j].iter() {
                w[j].push((A[N-1-j][N-i+j]*p+n)%M);
                w[j+1].push((A[N-1-j][N-i+j]*p+n)%M)
            }
        }
        v = w
    }
    v.iter().map(|a| a.iter().map(|n| n%M).collect::<Vec<_>>()).
                                                        collect::<Vec<_>>()
}

use std::cmp::max;

fn max_res(mut v: Vec<i64>, mut w: Vec<i64>, M: i64) -> i64 {
    let N = v.len();
    v.sort();
    w.sort_by(|a, b| b.cmp(a));
    let mut k: usize = 0;
    let mut l: usize = 0;
    let mut max_r: i64 = (v[N-1] + w[0]) % M;
    while k < N && l < N {
        let s = v[k] + w[l];
        if s < M {
            max_r = max(max_r, s);
            k += 1
        }
        else {
            l += 1
        }
    }
    max_r
}

fn F(M: i64, A: Matrix) -> i64 {
    let N = A.len();
    let v = upper_left(M, &A);
    let w = lower_right(M, &A);
    let mut max_r: i64 = 0;
    for i in 0..N {
        max_r = max(max_r, max_res(v[i].clone(), w[i].clone(), M))
    }
    max_r
}

fn main() {
    let (M, A) = read_input();
    println!("{}", F(M, A))
}