Problem:


Score : 700 points

Problem Statement

We have a board with an H \times W grid.
Each square in the grid is painted in black or white. The square at the i-th row from the top and j-th column from the left is black if the j-th character in S_i is #, and white if that character is ..

Snuke can perform the following operation on the grid any number of times:

Select a row or column in the grid, and invert the color of all the squares in that row or column (that is, black squares become white and vice versa).

Then, Snuke draws a rectangle along grid lines. Here, all the squares contained in the rectangle must be painted in black.

Find the maximum possible area of Snuke's rectangle when the operation is performed optimally.

Constraints

2 \leq H \leq 2000

2 \leq W \leq 2000

|S_i| = W

S_i consists of # and ..

Input

Input is given from Standard Input in the following format:

H W
S_1
S_2
:
S_H

Output

Print the maximum possible area of Snuke's rectangle.

Sample Input 1

3 3
..#
##.
.#.

Sample Output 1

6

If the first row from the top and the third column from the left are inverted, a 2 \times 3 rectangle can be drawn, as shown below:

Sample Input 2

4 4
....
....
....
....

Sample Output 2

16

Sample Input 3

10 8
##...#.#
##...#.#
..###.#.
#.##.#.#
.#..#.#.
..##.#.#
##.#.#..
...#.#..
###.#.##
###..###

Sample Output 3

27



Sample input:
3 3
..#
##.
.#.


Sample output:
6

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
from collections import deque

h,w = map(int,input().split())
s = []
for i in range(h):
  q = input().rstrip()
  s.append(list(q.replace('#','1').replace('.','0')))

chk = [[0]*(w-1) for i in range(h-1)]
s = [list(map(int,i)) for i in s]

for i in range(w-1):
  for j in range(h-1):
    chk[j][i] = s[j][i]^s[j+1][i]^s[j][i+1]^s[j+1][i+1]

def f(a):
  a += [0]
  stack = deque()
  ans = -1
  for i in range(w):
    if stack == deque():
        stack.append((a[i], i))
    elif stack[-1][0] < a[i]:
        stack.append((a[i], i))
    elif stack[-1][0] > a[i]:
      while stack and stack[-1][0] >= a[i]:
        x, y = stack.pop()
        ans = max((x+1)*(i-y+1), ans)
      stack.append((a[i], y))
  return ans
  
dp = [[0]*(w-1) for i in range(h-1)]
for i in range(w-1):
  dp[0][i] = chk[0][i]
  
for i in range(1,h-1):
  for j in range(w-1):
    if chk[i][j]:
      dp[i][j] = dp[i-1][j]+1

ans=max(h,w)
for i in range(h-1):
    ans=max(ans,f(dp[i]))
    
print(ans)

Submission status: Wrong Answer

Solution code:
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(max(ans,h,w))

main()

Submission status: Wrong Answer

Solution code:
import sys

input=sys.stdin.readline
p2D = lambda x: print(*x, sep="\n")
def MI(): return map(int, sys.stdin.readline().split())

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(max(ans,h,w))

main()

Submission status: Wrong Answer

Solution code:
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 status: Wrong Answer

Solution code:
import sys

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()] 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 status: Wrong Answer

Solution code:
import sys

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()] for _ in range(h)]
    # p2D(s)
    t = [[-1] * (w - 1) for _ in range(h - 1)]
    for i in range(h - 1):
        for j in range(w - 1):
            t[i][j] = 1 - (sum(s[i][j:j + 2]) + sum(s[i + 1][j:j + 2])) % 2
    # p2D(t)
    # print()
    for j in range(w - 1):
        for i in range(1, h - 1):
            if t[i][j]: t[i][j] = t[i - 1][j] + 1
    # p2D(t)
    ans = 0
    for i in range(h - 1):
        jtol = [0] * (w - 1)
        jtor = [0] * (w - 1)
        # 高さ、位置の順
        stack = [[-1, 0]]
        for j in range(w - 1):
            while stack[-1][0] >= t[i][j]: stack.pop()
            jtol[j] = stack[-1][1]
            stack.append([t[i][j], j + 1])
        stack = [[-1, w - 1]]
        for j in range(w - 2, -1, -1):
            while stack[-1][0] >= t[i][j]: stack.pop()
            jtor[j] = stack[-1][1]
            stack.append([t[i][j], j])
        for j in range(w - 1):
            tmp = (jtor[j] - jtol[j] + 1) * (t[i][j] + 1)
            if tmp > ans: ans = tmp
    print(ans)

main()

Submission status: Wrong Answer

Solution code:
import sys

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()] for _ in range(h)]
    #p2D(s)
    t = [[-1] * (w - 1) for _ in range(h - 1)]
    for i in range(h - 1):
        for j in range(w - 1):
            t[i][j] = 1 - (sum(s[i][j:j + 2]) + sum(s[i + 1][j:j + 2])) % 2
    #p2D(t)
    #print()
    for j in range(w - 1):
        for i in range(1, h - 1):
            if t[i][j]: t[i][j] = t[i - 1][j] + 1
    #p2D(t)
    ans = 0
    for i in range(h - 1):
        jtol = [0] * (w - 1)
        jtor = [0] * (w - 1)
        # 高さ、位置の順
        stack = [[0, 0]]
        for j in range(w - 1):
            while stack and stack[-1][0] >= t[i][j]: stack.pop()
            if stack: jtol[j] = stack[-1][1]
            stack.append([t[i][j], j + 1])
        stack = [[0, w - 1]]
        for j in range(w - 2, -1, -1):
            while stack and stack[-1][0] >= t[i][j]: stack.pop()
            if stack: jtor[j] = stack[-1][1]
            stack.append([t[i][j], j])
        max_in_row = 0
        for j in range(w - 1):
            tmp = (jtor[j] - jtol[j] + 1) * (t[i][j] + 1)
            if tmp > max_in_row: max_in_row = tmp
        if max_in_row > ans: ans = max_in_row
    print(ans)

main()

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

"""
・2x2内の偶奇が不変量。これが偶数なら、そこは単色でとれる
・単色でとれる領域を調べる -> 色変更なしに大きい長方形をとる問題になる
・ベースラインを固定すると、ヒストグラムの長方形の問題（アリ本）
"""

H,W = map(int,readline().split())
grid = read().replace(b'\r',b'').replace(b'\n',b'')

# 左上に集める
cnt = [0]*(H*W)
for x in range(H*W):
    if grid[x]==ord('#'):
        # その場
        cnt[x]^=1
        # 左
        if x%W:
            cnt[x-1]^=1
        # 上
        if x>=W:
            cnt[x-W]^=1
        if x%W and x>=W:
            cnt[x-W-1]^=1

max_area = 0
height = [1]*(W-1)
for i in range(H-1):
    for j in range(W-1):
        if cnt[W*i+j]:
            height[j]=1
        else:
            height[j]+=1
    # 最大長方形の変種。横幅を1乗せる
    stack = []
    for j,h in enumerate(height+[0]):
        while stack:
            prev_h = height[stack[-1]]
            if prev_h <= h:
                break
            left_end = stack.pop()
            area = (j-left_end+1) * height[left_end]
            if max_area < area:
                max_area = area
        stack.append(j)

# 幅1の長方形は2x2を素材としない
if max_area < max(W,H):
    max_area = max(W,H)
print(max_area)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3

def main():
    [H, W] = list(map(int, input().split()))
    S = []
    for i in range(H):
        S.append(input())

    pt = []
    for i in range(H - 1):
        pt.append([0] * W)

    for i in range(H - 1):
        r0 = S[i]
        r1 = S[i + 1]
        p = (r0[W - 1] == r1[W - 1])
        pti = pt[i]
        pti[W - 1] = 1
        c = 1
        for j in range(W - 2, -1, -1):
            if p == (r0[j] == r1[j]):
                c += 1
            else:
                p = not p
                c = 1
            pti[j] = c

    max_a = max(H, W)

    for j in range(W):
        i = 0
        while i < H - 1:
            ptij = pt[i][j]
            if ptij == 1:
                i += 1
                continue
            h = 2
            max_w = ptij
            max_a = max(max_a, max_w * h)
            i += 1
            while i < H - 1:
                ptij = pt[i][j]
                if ptij == 1:
                    i += 1
                    break
                h += 1
                max_w = min(max_w, ptij)
                max_a = max(max_a, max_w * h)
                i += 1



    print(max_a)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3

def main():
    [H, W] = list(map(int, input().split()))
    S = []
    for i in range(H):
        S.append(input())

    pt = []
    for i in range(H - 1):
        pt.append([0] * W)

    for i in range(H - 1):
        r0 = S[i]
        r1 = S[i + 1]
        p = (r0[W - 1] == r1[W - 1])
        pti = pt[i]
        pti[W - 1] = 1
        c = 1
        for j in range(W - 2, -1, -1):
            if p == (r0[j] == r1[j]):
                c += 1
            else:
                p = not p
                c = 1
            pti[j] = c

    max_a = max(H, W)

    for i in range(H - 1):
        pti = pt[i]
        for j in range(W):
            ptij = pti[j]
            if ptij == 1:
                continue
            max_w = ptij
            max_a = max(max_a, max_w * 2)
            for k in range(1, H - 1 - i):
                ptk = pt[k][j]
                if ptk == 1:
                    break
                max_w = min(max_w, ptk)
                max_a = max(max_a, max_w * (k + 2))

    print(max_a)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque
H,W=map(int,input().split())
S=[input() for i in range(H)]
table=[[0]*(W-1) for i in range(H-1)]
for i in range(W-1):
    for j in range(H-1):
        table[j][i]=(int(S[j][i]=='#')+int(S[j+1][i]=='#')+int(S[j][i+1]=='#')+int(S[j+1][i+1]=='#') +1 )%2

def get_rec(L):
    a = len(L)
    arr = L + [0]
    stack = deque()
    ans = -1
    for i in range(a + 1):
        #print(stack)
        if len(stack)==0:
            stack.append((arr[i], i))
        elif stack[-1][0] < arr[i]:
            stack.append((arr[i], i))
        elif stack[-1][0] > arr[i]:
            while len(stack) != 0 and stack[-1][0] >= arr[i]:
                x, y = stack.pop()
                ans = max((x+1) * (i - y+1), ans)
            # print(x,y,x*(i-y))
            stack.append((arr[i], y))
        #print(ans)
    return ans
dp=[[0]*(W-1) for i in range(H-1)]
for i in range(W-1):
    for j in range(H-1):
        if j==0:
            dp[0][i]=table[0][i]
            continue
        if table[j][i]==1:
            dp[j][i]=dp[j-1][i]+1
ans=-1
for j in range(H-1):
    ans=max(ans,get_rec(dp[j]))
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
H,W=map(int,input().split())
S=[input() for i in range(H)]
table=[[0]*(W-1) for i in range(H-1)]
for i in range(W-1):
    for j in range(H-1):
        table[j][i]=(int(S[j][i]=='#')+int(S[j+1][i]=='#')+int(S[j][i+1]=='#')+int(S[j+1][i+1]=='#') +1 )%2

def get_rec(L):
    a = len(L)
    arr = L + [0]
    stack = deque()
    ans = -1
    for i in range(a + 1):
        if len(stack)==0:
            stack.append((arr[i], i))
            continue
        while len(stack) != 0 and stack[-1][0] > arr[i]:
            x, y = stack.pop()
            ans = max((x+1) * (i - y+1), ans)
            # print(x,y,x*(i-y))
        stack.append((arr[i], i))
    return ans

dp=[[0]*(W-1) for i in range(H-1)]
for i in range(W-1):
    for j in range(H-1):
        if j==0:
            dp[0][i]=table[0][i]
            continue
        if table[j][i]==1:
            dp[j][i]=dp[j-1][i]+1
ans=-1
for j in range(H-1):
    ans=max(ans,get_rec(dp[j]))
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
H,W=map(int,input().split())
S=[input() for i in range(H)]
table=[[0]*(W-1) for i in range(H-1)]
for i in range(W-1):
    for j in range(H-1):
        table[j][i]=(int(S[j][i]=='#')+int(S[j+1][i]=='#')+int(S[j][i+1]=='#')+int(S[j+1][i+1]=='#') +1 )%2




def get_rec(L):
    a = len(L)
    arr = L + [0]
    stack = deque()
    ans = -1
    for i in range(a + 1):
        while len(stack) != 0 and stack[-1][0] > arr[i]:
            x, y = stack.pop()
            ans = max((x+1) * (i - y+1), ans)
            # print(x,y,x*(i-y))
        stack.append((arr[i], i))
    return ans

dp=[[0]*(W-1) for i in range(H-1)]
for i in range(W-1):
    for j in range(H-1):
        if j==0:
            dp[0][i]=table[0][i]
            continue
        if table[j][i]==1:
            dp[j][i]=dp[j-1][i]+1
ans=-1
for j in range(H-1):
    ans=max(ans,get_rec(dp[j]))
print(ans)
#print(table)
#print()
#print(dp)

Submission status: Wrong Answer

Solution code:
def inpl(): return [int(i) for i in input().split()]

H, W = inpl()
ans = max(H, W)
S = [input() for _ in range(H)]
T = [[0]*(W-1)]
for i in range(H-1):
    t = []
    for j in range(W-1):
        r = S[i][j:j+2] + S[i+1][j:j+2]
        t.append(r.count('.')%2)
    ts = [T[-1][i] + 1 if not k else 0 for i, k in enumerate(t) ]
    T.append(ts)
for iT in T[1:]:
    stack = []
    for i, l in enumerate(iT):
        while stack:
            w, h = stack[-1]
            if h > l:
                dw, dh = stack.pop()
                ans = max(ans, (dh+1)*(i-dw+1))
                continue
            break
        stack.append((i, l))
    while stack:
        dw, dh = stack.pop()
        ans = max(ans, (dh+1)*(i-dw+2))
print(ans)

Submission status: Wrong Answer

Solution code:
def inpl(): return [int(i) for i in input().split()]

H, W = inpl()
ans = max(H, W)
S = ''
for _ in range(H):
    S += input()
T = [[0]*(W-1)]
for i in range(H-1):
    t = []
    for j in range(W-1):
        r = S[i*W+j] + S[i*W+j+1] + S[(i+1)*W+j] + S[(i+1)*W+j+1]
        t.append(r.count('.')%2)
    ts = [0]*(W-1)
    for i, k in enumerate(t):
        if k:
            continue
        ts[i] = T[-1][i] + 1
    T.append(ts)
for iT in T[1:]:
    stack = []
    for i, l in enumerate(iT):
        while stack:
            w, h = stack[-1]
            if h > l:
                dw, dh = stack.pop()
                ans = max(ans, (dh+1)*(i-dw+2))
                continue
            break
        stack.append((i, l))
    while stack:
        dw, dh = stack.pop()
        ans = max(ans, (dh+1)*(i-dw+2))
print(ans)

Submission status: Time Limit Exceeded

Solution code:

"""
Writer: SPD_9X2
https://atcoder.jp/contests/arc081/tasks/arc081_d

長方形にできる必要十分条件は、
内側にある四つ角の周り全てに関して、周りにある黒が偶数個
→そのような条件を満たす四つ角グリッドを考えると最大長方形になる

幅1の長方形に関しては全て作れるので、ans初期値はmax(H,W)
"""
def Largest_rectangle_in_histgram(lis):

    stk = []

    ans = 0
    N = len(lis)

    for i in range(N):

        if len(stk) == 0:
            stk.append((lis[i],i))

        elif stk[-1][0] < lis[i]:
            stk.append((lis[i],i))

        elif stk[-1][0] == lis[i]:
            pass

        else:
            lastpos = None
            while len(stk) > 0 and stk[-1][0] > lis[i]:

                nh,np = stk[-1]
                lastpos = np
                del stk[-1]

                ans = max(ans , (nh+1) * (i-np+1))

            stk.append((lis[i] , lastpos))

    return ans

H,W = map(int,input().split())

S = []

for i in range(H):
    s = list(input())
    S.append(s)

#2*2以上
lis = [ [0] * (W-1) for i in range(H-1) ]

for i in range(H-1):

    for j in range(W-1):

        if S[i][j] == "#":
            lis[i][j] += 1
        if S[i+1][j] == "#":
            lis[i][j] += 1
        if S[i][j+1] == "#":
            lis[i][j] += 1
        if S[i+1][j+1] == "#":
            lis[i][j] += 1

        lis[i][j] %= 2

del S

hist =  [ [0] * W for i in range(H-1) ]
for i in range(H-1):
    for j in range(W-1):

        if lis[i][j] == 1:
            continue
        elif i == 0:
            hist[i][j] = 1
        else:
            hist[i][j] = hist[i-1][j] + 1

del lis

ans = max(H,W)
for i in range(H-1):
    ans = max(ans , Largest_rectangle_in_histgram(hist[i]))

print (ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

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()] 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):
        for j in range(w - 1):
            t[i][j] = 1 - (sum(s[i][j:j + 2]) + sum(s[i + 1][j:j + 2])) % 2
    # p2D(t)
    # print()
    for j in range(w - 1):
        for i in range(1, h - 1):
            if t[i][j]: t[i][j] = t[i - 1][j] + 1
    # p2D(t)
    ans = 0
    for i in range(h - 1):
        jtol = [0] * (w - 1)
        jtor = [0] * (w - 1)
        # 高さ、位置の順
        stack = [[-1, 0]]
        for j in range(w - 1):
            while stack[-1][0] >= t[i][j]: stack.pop()
            jtol[j] = stack[-1][1]
            stack.append([t[i][j], j + 1])

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

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

main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3

def main():
    [H, W] = list(map(int, input().split()))
    S = []
    for i in range(H):
        S.append(input())

    pt, ut, dt = [], [], []
    for i in range(H - 1):
        pt.append([0] * W)
        ut.append([0] * W)
        dt.append([0] * W)

    for i in range(H - 1):
        r0 = S[i]
        r1 = S[i + 1]
        p = (r0[W - 1] == r1[W - 1])
        pti = pt[i]
        pti[W - 1] = 1
        c = 1
        for j in range(W - 2, -1, -1):
            if p == (r0[j] == r1[j]):
                c += 1
            else:
                p = not p
                c = 1
            pti[j] = c

    for j in range(W):
        ut[0][j] = 1
    for i in range(1, H - 1):
        for j in range(W):
            if pt[i][j] <= pt[i - 1][j]:
                ut[i][j] = ut[i - 1][j] + 1
            else:
                ut[i][j] = 1
    for j in range(W):
        dt[H - 2][j] = 1
    for i in range(H - 3, -1, -1):
        for j in range(W):
            if pt[i][j] <= pt[i + 1][j]:
                dt[i][j] = dt[i + 1][j] + 1
            else:
                dt[i][j] = 1

    max_a = max(H, W)

    for i in range(H - 1):
        pti = pt[i]
        uti = ut[i]
        dti = dt[i]
        for j in range(W):
            max_a = max(max_a, pti[j] * (uti[j] + dti[j]))


    print(max_a)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def inpl(): return [int(i) for i in input().split()]

H, W = inpl()
ans = max(H, W)
S = ''
for _ in range(H):
    S += input()
T = [[0]*(W-1)]
for i in range(H-1):
    t = []
    for j in range(W-1):
        r = S[i*W+j] + S[i*W+j+1] + S[(i+1)*W+j] + S[(i+1)*W+j+1]
        t.append(r.count('.')%2)
    ts = [0]*(W-1)
    for i, k in enumerate(t):
        if k:
            continue
        ts[i] = T[-1][i] + 1
    T.append(ts)
for iT in T[1:]:
    stack = []
    for i, l in enumerate(iT):
        while stack:
            w, h = stack[-1]
            if h > l:
                dw, dh = stack.pop()
                ans = max(ans, (dh+1)*(i-dw+1))
                continue
            break
        stack.append((i, l))
    while stack:
        dw, dh = stack.pop()
        ans = max(ans, (dh+1)*(i-dw+2))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
S = [input() for _ in range(H)]

ans = max(H, W)

f = [1] * W
for i in range(1, H):
    f = [(f[j]+1) if (S[i-1][j:j+2] + S[i][j:j+2]).count('#') in [0,2,4] else 1 for j in range(W-1)] + [0]
    stk = []
    for j, v in enumerate(f):
        while len(stk) > 0 and f[stk[-1]] >= v:
            ans = max(ans, f[stk.pop()] * (j - (stk[-1] if len(stk) > 0 else -1)))
        stk.append(j)

print(ans)

Submission status: Memory Limit Exceeded

Solution code:

"""
Writer: SPD_9X2
https://atcoder.jp/contests/arc081/tasks/arc081_d

長方形にできる必要十分条件は、
内側にある四つ角の周り全てに関して、周りにある黒が偶数個
→そのような条件を満たす四つ角グリッドを考えると最大長方形になる

幅1の長方形に関しては全て作れるので、ans初期値はmax(H,W)
"""
def Largest_rectangle_in_histgram(lis):

    stk = []

    ans = 0
    N = len(lis)

    for i in range(N):

        if len(stk) == 0:
            stk.append((lis[i],i))

        elif stk[-1][0] < lis[i]:
            stk.append((lis[i],i))

        elif stk[-1][0] == lis[i]:
            pass

        else:
            lastpos = None
            while len(stk) > 0 and stk[-1][0] > lis[i]:

                nh,np = stk[-1]
                lastpos = np
                del stk[-1]

                ans = max(ans , (nh+1) * (i-np+1))

            stk.append((lis[i] , lastpos))

    return ans

H,W = map(int,input().split())

S = []

for i in range(H):
    s = list(input())
    S.append(s)

#2*2以上
lis = [ [0] * (W-1) for i in range(H-1) ]

for i in range(H-1):

    for j in range(W-1):

        if S[i][j] == "#":
            lis[i][j] += 1
        if S[i+1][j] == "#":
            lis[i][j] += 1
        if S[i][j+1] == "#":
            lis[i][j] += 1
        if S[i+1][j+1] == "#":
            lis[i][j] += 1

        lis[i][j] %= 2

hist =  [ [0] * W for i in range(H-1) ]
for i in range(H-1):
    for j in range(W-1):

        if lis[i][j] == 1:
            continue
        elif i == 0:
            hist[i][j] = 1
        else:
            hist[i][j] = hist[i-1][j] + 1

ans = max(H,W)
for i in range(H-1):
    ans = max(ans , Largest_rectangle_in_histgram(hist[i]))

print (ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from collections import deque

h,w = map(int,input().split())
s = []
for i in range(h):
  q = input().rstrip()
  s.append(q)

chk = [[0]*(w-1) for i in range(h-1)]
for i in range(w-1):
  for j in range(h-1):
    chk[j][i] = 1-int((s[j][i]=='#')^(s[j+1][i]=='#')^(s[j][i+1]=='#')^(s[j+1][i+1]=='#'))

def f(a):
  a += [0]
  stack = deque()
  ans = -1
  for i in range(w):
    if stack == deque():
        stack.append((a[i], i))
    elif stack[-1][0] < a[i]:
        stack.append((a[i], i))
    elif stack[-1][0] > a[i]:
      while stack and stack[-1][0] >= a[i]:
        x, y = stack.pop()
        ans = max((x+1)*(i-y+1), ans)
      stack.append((a[i], y))
  return ans
  
dp = [[0]*(w-1) for i in range(h-1)]
for i in range(w-1):
  dp[0][i] = chk[0][i]
  
for i in range(1,h-1):
  for j in range(w-1):
    if chk[i][j]:
      dp[i][j] = dp[i-1][j]+1

ans=max(h,w)
for i in range(h-1):
    ans=max(ans,f(dp[i]))
    
print(ans)

Submission status: Accepted

Solution code:
import sys

input=sys.stdin.readline
p2D = lambda x: print(*x, sep="\n")
def MI(): return map(int, sys.stdin.readline().split())

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):
            tij=ti[j]
            while stack[-1][0] >= tij: stack.pop()
            jtol[j] = stack[-1][1]
            stack.append([tij, j + 1])

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

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

main()

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

"""
・2x2内の偶奇が不変量。これが偶数なら、そこは単色でとれる
・単色でとれる領域を調べる -> 色変更なしに大きい長方形をとる問題になる
・ベースラインを固定すると、ヒストグラムの長方形の問題（アリ本）
"""

H,W = map(int,readline().split())
grid = read().replace(b'\r',b'').replace(b'\n',b'')

H,W

# 左上に集める
cnt = [0]*(H*W)
for x in range(H*W):
    if grid[x]==ord('#'):
        # その場
        cnt[x]^=1
        # 左
        if x%W:
            cnt[x-1]^=1
        # 上
        if x>=W:
            cnt[x-W]^=1
        if x%W and x>=W:
            cnt[x-W-1]^=1

max_area = 0
height = [1]*(W-1)
for i in range(H-1):
    for j in range(W-1):
        if cnt[W*i+j]:
            height[j]=1
        else:
            height[j]+=1
    # 最大長方形の変種。
    stack=[]
    for j,h in enumerate(height+[0]):
        while stack:
            prev_h = height[stack[-1]]
            if prev_h < h:
                break
            stack.pop()
            left_end = -1 if not stack else stack[-1]
            area = (j-left_end)*prev_h
            if max_area < area:
                max_area = area
        stack.append(j)

# 幅1の長方形は2x2を素材としない
if max_area < max(W,H):
    max_area = max(W,H)
print(max_area)