Submission #8830040

---

Source Code Expand

import sys

input=sys.stdin.readline
sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def main():
    h, w = MI()
    s = [[c == "#" for c in input()[:-1]] for _ in range(h)]
    if w == 2:
        s = [list(sc) for sc in zip(*s)]
        h, w = w, h
    # p2D(s)
    t = [[-1] * (w - 1) for _ in range(h - 1)]
    for i in range(h - 1):
        si = s[i]
        si1 = s[i + 1]
        t[i] = [1 - (sum(si[j:j + 2]) + sum(si1[j:j + 2])) % 2 for j in range(w - 1)]
    # p2D(t)
    # print()
    ti=t[0]
    for i in range(1, h - 1):
        ti1=ti
        ti=t[i]
        for j in range(w - 1):
            if ti[j]: ti[j] = ti1[j] + 1
    # p2D(t)
    ans = 0
    for i in range(h - 1):
        jtol = [0] * (w - 1)
        jtor = [0] * (w - 1)
        ti=t[i]
        # 高さ、位置の順
        stack = [[-1, 0]]
        for j in range(w - 1):
            h=ti[j]
            while stack[-1][0] >= h: stack.pop()
            jtol[j] = stack[-1][1]
            stack.append([h, j + 1])

        stack = [[-1, w - 1]]
        for j in range(w - 2, -1, -1):
            h=ti[j]
            while stack[-1][0] >= h: stack.pop()
            jtor[j] = stack[-1][1]
            stack.append([h, j])

        for j in range(w - 1):
            tmp = (jtor[j] - jtol[j] + 1) * (ti[j] + 1)
            if tmp > ans: ans = tmp
    print(ans)

main()

Submission Info

Judge Result