AOJ Largest Rectangle
解法
各列についてヒストグラムに内接する最大長方形を求める。
コード
use std::cmp; use std::collections::VecDeque; trait TopQueue<T> { fn top(&self) -> &T; } impl<T> TopQueue<T> for VecDeque<T> { fn top(&self) -> &T { assert!(!self.is_empty()); self.iter().next().unwrap() } } fn f(hist: &Vec<usize>) -> usize { let n = hist.len(); let mut ans = 0; let mut q: VecDeque<(usize, usize)> = VecDeque::new(); for i in 0..n { let mut reachable_min = i; while !q.is_empty() && q.top().1 > hist[i] { let (pos, height) = q.pop_front().unwrap(); reachable_min = pos; ans = cmp::max(ans, (i - reachable_min) * height); } if q.is_empty() || q.top().1 < hist[i] { q.push_front((reachable_min, hist[i])); } } while !q.is_empty() { let (pos, height) = q.pop_front().unwrap(); ans = cmp::max(ans, (n - pos) * height); } ans } fn main() { let mut sc = Scanner::new(); let h = sc.read(); let w = sc.read(); let mut c = vec![vec![false; w]; h]; for i in 0..h { for j in 0..w { c[i][j] = sc.read::<usize>() == 0; } } let mut hist = vec![vec![0; w]; h]; for i in 0..h { for j in 0..w { if !c[i][j] { continue; } if i == 0 { hist[i][j] = 1; } else { hist[i][j] = hist[i - 1][j] + 1; } } } let mut ans = 0; for i in 0..h { ans = cmp::max(ans, f(&hist[i])); } println!("{}", ans); } struct Scanner { ptr: usize, length: usize, buf: Vec<u8>, small_cache: Vec<u8>, } #[allow(dead_code)] impl Scanner { fn new() -> Scanner { Scanner { ptr: 0, length: 0, buf: vec![0; 1024], small_cache: vec![0; 1024], } } fn load(&mut self) { use std::io::Read; let mut s = std::io::stdin(); self.length = s.read(&mut self.buf).unwrap(); } fn byte(&mut self) -> u8 { if self.ptr >= self.length { self.ptr = 0; self.load(); if self.length == 0 { self.buf[0] = b'\n'; self.length = 1; } } self.ptr += 1; return self.buf[self.ptr - 1]; } fn is_space(b: u8) -> bool { b == b'\n' || b == b'\r' || b == b'\t' || b == b' ' } fn read_vec<T>(&mut self, n: usize) -> Vec<T> where T: std::str::FromStr, T::Err: std::fmt::Debug, { (0..n).map(|_| self.read()).collect() } fn usize_read(&mut self) -> usize { self.read() } fn read<T>(&mut self) -> T where T: std::str::FromStr, T::Err: std::fmt::Debug, { let mut b = self.byte(); while Scanner::is_space(b) { b = self.byte(); } for pos in 0..self.small_cache.len() { self.small_cache[pos] = b; b = self.byte(); if Scanner::is_space(b) { return String::from_utf8_lossy(&self.small_cache[0..(pos + 1)]) .parse() .unwrap(); } } let mut v = self.small_cache.clone(); while !Scanner::is_space(b) { v.push(b); b = self.byte(); } return String::from_utf8_lossy(&v).parse().unwrap(); } }