ARC081-F
import java.io.IOException; | |
import java.io.InputStream; | |
import java.io.PrintWriter; | |
import java.util.Arrays; | |
import java.util.InputMismatchException; | |
public class F { | |
public static void main(String[] args) { | |
InputReader in = new InputReader(System.in); | |
PrintWriter out = new PrintWriter(System.out); | |
int H = in.nextInt(); | |
int W = in.nextInt(); | |
int[][] table = new int[H][W]; | |
for (int i = 0; i < H ; i++) { | |
char[] c = in.nextToken().toCharArray(); | |
for (int j = 0; j < W ; j++) { | |
table[i][j] = c[j] == '.' ? 0 : 1; | |
} | |
} | |
int[][] diff = new int[H][W-1]; | |
for (int i = 0 ; i < H ; i++) { | |
for (int j = 0; j+1 < W; j++) { | |
diff[i][j] = table[i][j] ^ table[i][j+1]; | |
} | |
} | |
W--; | |
int[] bottom = new int[W]; | |
for (int j = 0; j < W ; j++) { | |
int shouldSameTo = 0; | |
while (bottom[j] < H && diff[bottom[j]][j] == diff[shouldSameTo][j]) { | |
bottom[j]++; | |
} | |
} | |
int answer = Math.max(H, W+1); | |
int[] height = new int[W]; | |
for (int i = 0 ; i < H ; i++) { | |
for (int j = 0; j < W ; j++) { | |
height[j] = bottom[j] - i; | |
} | |
answer = Math.max(answer, solve(height)); | |
for (int j = 0; j < W ; j++) { | |
if (bottom[j] == i+1) { | |
int shouldSameTo = bottom[j]; | |
while (bottom[j] < H && diff[bottom[j]][j] == diff[shouldSameTo][j]) { | |
bottom[j]++; | |
} | |
} | |
} | |
} | |
out.println(answer); | |
out.flush(); | |
} | |
static int solve(int[] a) { | |
int n = a.length; | |
int[] stk = new int[n+1]; | |
int head = 0; | |
int[] l = new int[n]; | |
for (int i = 0 ; i < n ; i++) { | |
while (head > 0 && a[stk[head-1]] >= a[i]) { | |
head--; | |
} | |
l[i] = head == 0 ? 0 : stk[head-1]+1; | |
stk[head++] = i; | |
} | |
int[] r = new int[n]; | |
head = 0; | |
for (int i = n-1 ; i >= 0 ; i--) { | |
while (head > 0 && a[stk[head-1]] >= a[i]) { | |
head--; | |
} | |
r[i] = head == 0 ? n : stk[head-1]; | |
stk[head++] = i; | |
} | |
int max = 0; | |
for (int i = 0; i < n ; i++) { | |
max = Math.max(max, a[i] * (r[i] - l[i] + 1)); | |
} | |
return max; | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment