Submission #3584545
Source Code Expand
/// Thank you tanakh!!!
/// https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8
macro_rules! input {
(source = $s:expr, $($r:tt)*) => {
let mut iter = $s.split_whitespace();
input_inner!{iter, $($r)*}
};
($($r:tt)*) => {
let mut s = {
use std::io::Read;
let mut s = String::new();
std::io::stdin().read_to_string(&mut s).unwrap();
s
};
let mut iter = s.split_whitespace();
input_inner!{iter, $($r)*}
};
}
macro_rules! input_inner {
($iter:expr) => {};
($iter:expr, ) => {};
($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
let $var = read_value!($iter, $t);
input_inner!{$iter $($r)*}
};
}
macro_rules! read_value {
($iter:expr, ( $($t:tt),* )) => {
( $(read_value!($iter, $t)),* )
};
($iter:expr, [ $t:tt ; $len:expr ]) => {
(0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
};
($iter:expr, chars) => {
read_value!($iter, String).chars().collect::<Vec<char>>()
};
($iter:expr, usize1) => {
read_value!($iter, usize) - 1
};
($iter:expr, $t:ty) => {
$iter.next().unwrap().parse::<$t>().expect("Parse error")
};
}
use std::cmp;
fn main() {
input!(h: usize, w: usize, s: [chars; h]);
let mut rectangle = vec![vec![false; w - 1]; h - 1];
for h in 0..(h - 1) {
for w in 0..(w - 1) {
let mut count = 0;
for h in h..(h + 2) {
for w in w..(w + 2) {
if s[h][w] == '#' {
count += 1;
}
}
}
rectangle[h][w] = count % 2 == 0;
}
}
let mut ans = max_rectangle::maximize(&rectangle);
ans = cmp::max(ans, h);
ans = cmp::max(ans, w);
println!("{}", ans);
}
pub mod max_rectangle {
use std::cmp;
use std::collections::VecDeque;
fn calc_area(h: usize, w: usize) -> usize {
(h + 1) * (w + 1)
}
fn calc(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 let Some((pos, height)) = q.pop_front() {
if height <= hist[i] {
q.push_front((pos, height));
break;
}
reachable_min = pos;
ans = cmp::max(
ans,
/* (i - reachable_min) * height */ calc_area(i - reachable_min, height),
);
}
if q.is_empty() || q.iter().next().unwrap().1 < hist[i] {
q.push_front((reachable_min, hist[i]));
}
}
while let Some((pos, height)) = q.pop_front() {
ans = cmp::max(
ans,
/* (n - pos) * height */ calc_area(n - pos, height),
);
}
ans
}
pub fn maximize(map: &Vec<Vec<bool>>) -> usize {
let h = map.len();
let w = map[0].len();
let mut hist = vec![vec![0; w]; h];
for i in 0..h {
for j in 0..w {
if !map[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, calc(&hist[i]));
}
ans
}
}
Submission Info
Submission Time
2018-11-11 16:18:56+0900
Task
F - Flip and Rectangles
User
kenkoooo
Language
Rust (1.15.1)
Score
700
Code Size
3782 Byte
Status
AC
Exec Time
174 ms
Memory
69880 KB
Compile Error
warning: variable does not need to be mutable, #[warn(unused_mut)] on by default
--> ./Main.rs:9:13
|
9 | let mut s = {
| ^^^^^
...
55 | input!(h: usize, w: usize, s: [chars; h]);
| ------------------------------------------ in this macro invocation
Judge Result
Set Name
Sample
All
Score / Max Score
0 / 0
700 / 700
Status
Set Name
Test Cases
Sample
sample1.txt, sample2.txt, sample3.txt
All
sample1.txt, sample2.txt, sample3.txt, 1.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 2.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt, 27.txt, 28.txt, 29.txt, 3.txt, 30.txt, 31.txt, 32.txt, 33.txt, 34.txt, 4.txt, 5.txt, 6.txt, 7.txt, 8.txt, 9.txt, sample1.txt, sample2.txt, sample3.txt
Case Name
Status
Exec Time
Memory
1.txt
AC
2 ms
4352 KB
10.txt
AC
164 ms
69880 KB
11.txt
AC
66 ms
39164 KB
12.txt
AC
124 ms
69880 KB
13.txt
AC
125 ms
69880 KB
14.txt
AC
125 ms
69880 KB
15.txt
AC
125 ms
69880 KB
16.txt
AC
126 ms
69880 KB
17.txt
AC
125 ms
69880 KB
18.txt
AC
170 ms
69880 KB
19.txt
AC
139 ms
69880 KB
2.txt
AC
2 ms
4352 KB
20.txt
AC
144 ms
69880 KB
21.txt
AC
143 ms
69880 KB
22.txt
AC
143 ms
69880 KB
23.txt
AC
148 ms
69880 KB
24.txt
AC
125 ms
69880 KB
25.txt
AC
125 ms
69880 KB
26.txt
AC
171 ms
69880 KB
27.txt
AC
159 ms
69880 KB
28.txt
AC
153 ms
69880 KB
29.txt
AC
124 ms
69880 KB
3.txt
AC
172 ms
69880 KB
30.txt
AC
122 ms
69880 KB
31.txt
AC
123 ms
69880 KB
32.txt
AC
125 ms
69880 KB
33.txt
AC
125 ms
69880 KB
34.txt
AC
125 ms
69880 KB
4.txt
AC
172 ms
69880 KB
5.txt
AC
2 ms
4352 KB
6.txt
AC
3 ms
4352 KB
7.txt
AC
173 ms
69880 KB
8.txt
AC
174 ms
69880 KB
9.txt
AC
163 ms
69880 KB
sample1.txt
AC
2 ms
4352 KB
sample2.txt
AC
2 ms
4352 KB
sample3.txt
AC
2 ms
4352 KB