competitive_programming_rs/math/
max_rectangle.rs

1pub mod max_rectangle {
2    use std::cmp;
3    use std::collections::VecDeque;
4
5    fn calc(hist: &[usize]) -> usize {
6        let n = hist.len();
7        let mut ans = 0;
8        let mut q: VecDeque<(usize, usize)> = VecDeque::new();
9
10        for (i, &hist) in hist.iter().enumerate() {
11            let mut reachable_min = i;
12            while let Some((pos, height)) = q.pop_front() {
13                if height <= hist {
14                    q.push_front((pos, height));
15                    break;
16                }
17                reachable_min = pos;
18                ans = cmp::max(ans, (i - reachable_min) * height);
19            }
20
21            if q.is_empty() || q.iter().next().unwrap().1 < hist {
22                q.push_front((reachable_min, hist));
23            }
24        }
25        while let Some((pos, height)) = q.pop_front() {
26            ans = cmp::max(ans, (n - pos) * height);
27        }
28        ans
29    }
30
31    pub fn maximize(map: &[Vec<bool>]) -> usize {
32        let h = map.len();
33        let w = map[0].len();
34        let mut hist = vec![vec![0; w]; h];
35        for i in 0..h {
36            for j in 0..w {
37                if !map[i][j] {
38                    continue;
39                }
40                if i == 0 {
41                    hist[i][j] = 1;
42                } else {
43                    hist[i][j] = hist[i - 1][j] + 1;
44                }
45            }
46        }
47
48        let mut ans = 0;
49        for hist in hist.iter() {
50            ans = cmp::max(ans, calc(hist));
51        }
52        ans
53    }
54}
55
56#[cfg(test)]
57mod test {
58    use super::*;
59    use crate::utils::test_helper::Tester;
60
61    #[test]
62    fn solve_dpl_3_b() {
63        let tester = Tester::new("./assets/DPL_3_B/in/", "./assets/DPL_3_B/out/");
64
65        tester.test_solution(|sc| {
66            let h: usize = sc.read();
67            let w: usize = sc.read();
68
69            let mut c = vec![vec![false; w]; h];
70            for i in 0..h {
71                for j in 0..w {
72                    c[i][j] = sc.read::<usize>() == 0;
73                }
74            }
75
76            let ans = max_rectangle::maximize(&c);
77            sc.write(format!("{}\n", ans));
78        });
79    }
80}
competitive_programming_rs/math/max_rectangle.rs

competitive_programming_rs/math/
max_rectangle.rs
