1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
use std::{cmp::min, io, mem};

fn flip<T>(tup: &mut (T, T)) {
    mem::swap(&mut tup.0, &mut tup.1);
}

fn solve(data: Vec<Vec<u32>>) -> u32 {
    let mut res = 0;
    let mut tup = (Vec::new(), Vec::new());
    tup.0.resize(data.last().unwrap().len(), 0);
    for idx in (0..data.len()).rev() {
        let curr_data = &data[idx];
        let next_data = if idx > 0 { &data[idx-1] } else { &Vec::new() };
        let curr_buf = &mut tup.0;
        let next_buf = &mut tup.1;

        let mut curr_res = 0;
        next_buf.clear();
        next_buf.resize(next_data.len(), 0);
        for (val, cnt) in curr_data.iter().copied().zip(curr_buf.iter().copied()) {
            let cnt = cnt.max(1);
            curr_res += cnt;
            if val > 0 {
                next_buf[(val-1) as usize] += cnt;
            }
        }
        // eprintln!("next_buf: {:?}", next_buf);

        res = res.max(curr_res);

        flip(&mut tup);
    }


    res
}

pub fn main() -> io::Result<()> {
    let mut buf = String::new();
    io::stdin().read_line(&mut buf)?;
    let [cnt, init] = buf.split_whitespace().map(|x| x.parse().unwrap()).collect::<Vec<u32>>()[..] else {
        panic!("Expected two numbers!")
    };
    let mut data = Vec::new();
    data.push(
        (0..init).map(|x| 0).collect()
    );

    for _ in 2..=cnt {
        buf.clear();
        io::stdin().read_line(&mut buf)?;
        data.push(buf.split_whitespace().map(|x| x.parse().unwrap()).skip(1).collect());
    }

    // eprintln!("data: {:?}", data);

    println!("{}", solve(data));
    Ok(())
}