Problem:


Largest Rectangle

  Given a matrix (H &times; W) which contains only 1 and 0, find the area of the largest rectangle which only contains 0s.

Input

H W
c1,1 c1,2 ... c1,W
c2,1 c2,2 ... c2,W
:
cH,1 cH,2 ... cH,W

  In the first line, two integers H and W separated by a space character are given. In the following H lines, ci,j, elements of the H &times; W matrix, are given.

Output

  Print the area (the number of 0s) of the largest rectangle.

Constraints

 1 ≤ H, W ≤ 1,400
	

Sample Input

4 5
0 0 1 0 0
1 0 0 0 0
0 0 0 1 0
0 0 0 1 0

Sample Output

6



Sample input:
4 5
0 0 1 0 0
1 0 0 0 0
0 0 0 1 0
0 0 0 1 0


Sample output:
6

Submission status: Accepted

Solution code:
from sys import stdin
from collections import deque
H, W = map(int, stdin.readline().split())
C = [list(map(int, stdin.readline().split())) for i in range(H)]
prev = [0] * W
def height(C):
    global prev
    P = []
    for i in range(W):
        if C[-1][i] == 1:
            p = 0
        else:
            p = prev[i] + 1
        P.append(p)
    prev = P[:]
    return P
def square(C):
    P = height(C)
    G = deque()
    L = deque()
    for i, v in enumerate(P):
        if not L or v > L[-1][1]:
            L.append((i, v))
        elif v < L[-1][1]:
            k = i - 1
            while L and v < L[-1][1]:
                a = L.pop()
                G.append((k - a[0] + 1) * a[1])
            L.append((a[0], v))
    len_P = len(P)
    while L:
        a = L.pop()
        G.append((len_P - a[0]) * a[1])
    return max(G)
print(max([square(C[:i + 1]) for i in range(H)]))

Submission status: Accepted

Solution code:
from sys import stdin
from collections import deque
H, W = map(int, stdin.readline().split())
C = [list(map(int, stdin.readline().split())) for i in range(H)]
prev = [0] * W
def height(C):
    global prev
    P = [0 if C[-1][i] == 1 else prev[i] + 1 for i in range(W)]
    prev = P[:]
    return P
def square(C):
    P = height(C)
    G = deque()
    L = deque()
    for i, v in enumerate(P):
        if not L or v > L[-1][1]:
            L.append((i, v))
        elif v < L[-1][1]:
            k = i - 1
            while L and v < L[-1][1]:
                a = L.pop()
                G.append((k - a[0] + 1) * a[1])
            L.append((a[0], v))
    len_P = len(P)
    while L:
        a = L.pop()
        G.append((len_P - a[0]) * a[1])
    return max(G)
print(max([square(C[:i + 1]) for i in range(H)]))

Submission status: Accepted

Solution code:
from sys import stdin
from collections import deque
readline = stdin.readline
h, w = map(int, readline().split())
w += 1
dp = [list(map(int, readline().split())) + [1] for _ in range(h)]
for i in range(h):
    for j in range(w):
        dp[i][j] ^= 1
for i in range(1, h):
    for j in range(w):
        if dp[i][j]:
            dp[i][j] += dp[i - 1][j]
max_s = 0
for i in range(h):
    stack = deque()
    for j in range(w):
        if (stack[-1][0] if stack else 0) < dp[i][j]:
            stack.append((dp[i][j], j))
        elif stack and stack[-1][0] > dp[i][j]:
            while stack and stack[-1][0] > dp[i][j]:
                height, l = stack.pop()
                s = height * (j - l)
                if max_s < s:
                    max_s = s
            if dp[i][j]:
                stack.append((dp[i][j], l))
print(max_s)

Submission status: Accepted

Solution code:
from sys import stdin
from collections import deque
def judge(n,hs):
    stack = deque()
    ans = 0
    for i, h in enumerate(hs):
        j = -1
        while stack and stack[-1][1] > h:
            j, h2 = stack.pop()
            ans = max(ans, (i - j) * h2)
        if not stack or stack[-1][1] < h:
            stack.append((i if j == -1 else j, h))
    ans = max(ans, max((n - j) * h2 for j, h2 in stack))
    return ans
H,W = map(int,stdin.readline().split())
hs = [0]*W
result = 0
for i in range(H):
    ht = list(map(int, stdin.readline().split()))
    hs = list(map(lambda x,y:(x+1)*abs(y-1),hs,ht))
    result = max(result,judge(W,hs))
print(result)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from itertools import product

def rectangle_in_histgram(H):

    def calc(i, h):
        tmp_max = 0
        while stack[-1][1] > h:
            pi, ph = stack.pop()
            tmp_max = max(tmp_max, (i-pi)*ph)
            if len(stack) == 0:
                break

        if len(stack) == 0:
            stack.append([pi, h])
        elif stack[-1][1] < h:
            stack.append([pi, h])
        return tmp_max
    
    stack = [] # loc, height
    S_max = 0
    
    for i, h in enumerate(H):
        if len(stack) == 0:
            stack.append([i, h])
        elif h > stack[-1][1]:
            stack.append([i, h])
        elif h == stack[-1][1]:
            pass
        else:
            tmp_max = calc(i, h)
            S_max = max(S_max, tmp_max)

    tmp_max = calc(i+1, 0)
    S_max = max(S_max, tmp_max)
    return S_max


H, W = tuple(map(int, input().split()))
C = [tuple(map(int, input().split())) for _ in range(H)]
A = [[1]*W for _ in range(H)]
for h, w in product(range(H), range(W)):
    if C[h][w] == 1:
        A[h][w] = 0

for h, w in product(range(1, H), range(W)):
    if C[h][w] == 0:
        A[h][w] = A[h-1][w] + 1

result = 0
for a in A:
    result = max(result, rectangle_in_histgram(a))

print(result)

Submission status: Accepted

Solution code:
from collections import deque

def rectangle(n, hs): #n:?¨????hs: ???????????°??????
    stack = deque() # stack = (j, h) ????????¨?????????????´??????????
    ans = 0
    for i, h in enumerate(hs):
        j = -1
        while stack and stack[-1][1] > h:
            j, h2 = stack.pop()
            ans = max(ans, (i-j) * h2)
            
        if not stack or stack[-1][1] < h: #stack?????????????????????stack?????????????????????"??????h"?????????????????°?????????????????????????°????????????°???????£???¨??????stack????????????
            stack.append( (i if j == -1 else j, h))
        
    ans = max(ans, max((n-j) * h2 for j, h2 in stack))
    
    return ans
    
H, W = map(int, input().split())
hs = [0] * W
result = 0

for i in range(H):
    ht = list(map(int, input().split()))
    hs = list(map(lambda x, y: (x+1) * abs(y-1), hs, ht)) #???????????°???????????????
    result = max(result, rectangle(W, hs))
    
print(result)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
'''
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_3_A&lang=jp
???????¨???????
?????§????????¢
??£?????¢??????????§£????????????????????????????????°????????§?§£???????????????
'''

H, W = map(int, input().split())
C = list()
maxArea = 0

for h in range(H):
    C.append(list(map(int, input().split())))

#buf = [[-1 for w in range(W)] for h in range(H)]
T = [[float('inf') for w in range(W)] for h in range(H)]
for h in range(H):
    for w in range(W):
        if C[h][w] == 1:
            T[h][w] = 0
        else:
            if h==0:
                T[h][w] = 1
                continue
            T[h][w] = T[h-1][w] + 1

class Rectangle():
    def __init__(self, height, pos):
        self.height = height
        self.pos = pos

def getLargestRectangle(size, buff):
    S = list()
    maxv = 0
    buff.append(0)
    for w in range(size+1):
        rect = Rectangle(buff[w], w)
        if len(S) ==0:
            S.append(rect)
            #print("len(S)=0,w=",w)
        else:
            if S[-1].height < rect.height:
                S.append(rect)
                #print("S[-1].height < rect.height,w=",w)
            elif S[-1].height > rect.height:
                target = w
                while len(S) > 0 and S[-1].height >= rect.height:
                    #print("S[-1].height > rect.height,w=",w,",target=",target)
                    pre = S.pop()
                    area = pre.height * (w - pre.pos)
                    maxv = max(maxv, area)
                    target = pre.pos
                rect.pos = target
                S.append(rect)
    return maxv

#print(T)

ans = 0
for h in range(H):
    ans = max(ans, getLargestRectangle(W, T[h]))


print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

from itertools import chain

if __name__ == '__main__':

    H, W = map(int, input().split())
    C = []
    hist = []
    for i in range(H):
        l = input().split()
        C.append([int(x) for x in l])
        hist.append([(int(x) + 1) % 2 for x in l])

    for i in range(1, H):
        for j in range(W):
            if C[i][j] == 0:
                hist[i][j] = hist[i - 1][j] + 1
    
    S = []
    max_area = 0
    for i in range(H):
        for j in range(W):
            rect = [j, hist[i][j]]
            if not S:
                S.append(rect)
            elif S[-1][1] < rect[1]:
                S.append(rect)
            elif S[-1][1] > rect[1]:
                while S and S[-1][1] > rect[1]:
                    post_rect = S.pop()
                    area = post_rect[1] * (j - post_rect[0])
                    max_area = max(max_area, area)
                S.append([post_rect[0], rect[1]])
        while S:
            post_rect = S.pop()
            area = post_rect[1] * (W - post_rect[0])
            max_area = max(max_area, area)

    print(max_area)

Submission status: Accepted

Solution code:
h, w = map(int, input().split())

mp = []
for _ in range(h):
  lst = list(map(int, input().split()))
  cum = []
  acc = 0
  for i in lst:
    if not i:
      acc += 1
    else:
      acc = 0
    cum.append(acc)
  mp.append(cum)
mp.append([-1] * w)
ans = 0

#print(*mp, sep="\n")
for i in range(w - 1, -1, -1):
  stack = []
#  print(ans)
  for j in range(h + 1):
#    print(stack)
    score = mp[j][i]
    if not stack:
      stack.append((score, j))
    else:
      last_score, last_ind = stack[-1][0], stack[-1][1]
      if score > last_score:
        stack.append((score, j))
      elif score == last_score:
        continue
      else:
        while stack and stack[-1][0] > score:
          last_score, last_ind = stack.pop()
          ans = max(ans, last_score * (j - last_ind))
        if not stack:
          stack.append((score, last_ind))
        elif stack[-1][0] == score:
          pass
        else:
          stack.append((score, last_ind))

print(ans)

Submission status: Accepted

Solution code:
h, w = map(int, input().split())

mp = []
for _ in range(h):
  lst = list(map(int, input().split()))
  cum = []
  acc = 0
  for i in lst:
    if not i:
      acc += 1
    else:
      acc = 0
    cum.append(acc)
  mp.append(cum)
mp.append([-1] * w)
ans = 0

for i in range(w):
  stack = []

  for j in range(h + 1):
    score = mp[j][i]

    if not stack:
      stack.append((score, j))

    else:
      last_score, last_ind = stack[-1][0], stack[-1][1]
      if score > last_score:
        stack.append((score, j))
      
      elif score == last_score:
        continue
      
      else:
        while stack != [] and stack[-1][0] >= score:
          last_score, last_ind = stack.pop()
          ans = max(ans, last_score * (j - last_ind))
        stack.append((score, last_ind))

print(ans)

Submission status: Accepted

Solution code:
h,w = map(int,input().split())
c = [list(map(int,input().split())) for _ in range(h)]

T = [[0]*(w+1) for _ in range(h)]

for j in range(w):
    for i in range(h):
        if c[i][j] == 1:
            continue
        else:
            T[i][j] = T[i-1][j]+1 if i>0 else 1
            
maxv = 0
for i in range(h):
    S = []
    
    for j in range(w+1):
        rect = [T[i][j],j]
        if S:
            if S[-1][0]<rect[0]:
                S.append(rect)
            elif S[-1][0]>rect[0]:
                target = j
                while(S and S[-1][0]>=rect[0]):
                    pre = S.pop()
                    area = pre[0]*(j-pre[1])
                    maxv = max(maxv,area)
                    target = pre[1]
                rect[1] = target
                S.append(rect)
        else:
            S.append(rect)
            
print(maxv)

Submission status: Accepted

Solution code:
import sys
# import re
import math
import collections
# import decimal
import bisect
import itertools
import fractions
# import functools
import copy
# import heapq
import decimal
# import statistics
import queue

# import numpy as np

sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===

def largestRectangInHistgram(heights):
    stack = [-1]
    maxArea = 0

    for i in range(len(heights)):
        # we are saving indexes in stack that is why we comparing last element in stack
        # with current height to check if last element in stack not bigger then
        # current element
        while stack[-1] != -1 and heights[stack[-1]] > heights[i]:
            lastElementIndex = stack.pop()
            maxArea = max(maxArea, heights[lastElementIndex] * (i - stack[-1] - 1))
        stack.append(i)

    # we went through all elements of heights array
    # let's check if we have something left in stack
    while stack[-1] != -1:
        lastElementIndex = stack.pop()
        maxArea = max(maxArea, heights[lastElementIndex] * (len(heights) - stack[-1] - 1))

    return maxArea


def main():
    h, w = ns()
    mat = [na() for _ in range(h)]

    current = [0 for _ in range(w + 1)]

    ans = 0
    for i in range(h):
        for j in range(w):
            current[j] = current[j] + (mat[i][j] ^ 1) if mat[i][j]==0 else 0
        # current = [0] + current + [0]
        ans = max(ans, largestRectangInHistgram(current))

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque

H,W = map(int,input().split())
W += 1
M = [[0]*(W+1) for _ in range(H+1)]
for i in range(H):
    M[i+1][1:] = list(map(int,input().split())) + [1]

h_table = [[0]*(W+1) for _ in range(H+1)]
for h in range(1,H+1):
    for w in range(1,W+1):
        if M[h][w] == 0:
            h_table[h][w] = h_table[h-1][w] +1
        else:
            h_table[h][w] = 0

max_S = 0
for h in range(1,H+1):
    stuck = deque()
    hist = h_table[h][:]
    for w in range(1,W+1):
        if stuck == deque() or stuck[-1][0] < hist[w]:
            stuck.append([hist[w],w])
        elif stuck[-1][0] > hist[w]:
            while 1:
                rect = stuck.pop()
                max_S = max(max_S,rect[0]*(w-rect[1]))
                if stuck == deque() or stuck[-1][0] <= hist[w]:
                    break
            if stuck == deque() or stuck[-1][0] < hist[w]:
                stuck.append([hist[w],rect[1]])
            

print(max_S)

Submission status: Accepted

Solution code:

def resolve():
    def get_largest_rectangle(hist: list):
        hist = hist.copy()
        hist.append(0)
        ret = 0
        stack = []
        for i, v in enumerate(hist):
            if len(stack) == 0:
                stack.append((i, v))
            elif stack[-1][1] < v:
                stack.append((i, v))
            elif stack[-1][1] > v:
                while stack and stack[-1][1] > v:
                    i_left, h = stack.pop()
                    ret = max(ret, (i - i_left)*h)
                stack.append((i_left, v))
        return ret


    H, W = map(int, input().split())
    AB = [list(map(int, input().split())) for _ in range(H)]
    T = [[0]*W for _ in range(H)]

    for j in range(W):
        seq = 0
        for i in range(H):
            if AB[i][j] == 1:
                T[i][j] = 0
                seq = 0
            else:
                T[i][j] = seq + 1
                seq += 1
    ans = 0
    for t in T:
        ans = max(ans, get_largest_rectangle(t))
    print(ans)

if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
from sys import stdin
readline = stdin.readline


h, w = map(int, readline().split())
w += 1
dp = [list(map(int, readline().split())) + [1] for _ in range(h)]

for i in range(h):
    for j in range(w):
        dp[i][j] ^= 1
    
for i in range(1, h):
    for j in range(w):
        if dp[i][j]:
            dp[i][j] += dp[i - 1][j]

max_s = 0
for i in range(h):
    stack = []
    for j in range(w):
        if (stack[-1][0] if stack else 0) < dp[i][j]:
            stack.append((dp[i][j], j))
        elif stack and stack[-1][0] > dp[i][j]:
            while stack and stack[-1][0] > dp[i][j]:
                height, l = stack.pop()
                s = height * (j - l)
                if max_s < s:
                    max_s = s
            if dp[i][j]:
                stack.append((dp[i][j], l))
print(max_s)

Submission status: Accepted

Solution code:
# DPL_3_B: Largest Rectangle
import sys
H, W = map(int, sys.stdin.readline().strip().split())

C = []
for h in range(H):
    c = list(map(int, sys.stdin.readline().strip().split()))
    C.append(c)

# 列方向のdp
dp = [[0] * (W + 1) for _ in range(H)]
for h in range(H):
    for w in range(W + 1):  # 長方形の面積探査時に一番右端が0だと都合がいい
        if w == W:
            dp[h][w] = 0
            continue
        if C[h][w] == 1:
           dp[h][w] = 0
        elif h == 0:  # 0行目は上の行が存在しないので別処理
           dp[0][w] = 1
        else:
           dp[h][w] = dp[h-1][w] + 1

# 長方形を求める
ans = 0
for h in range(H):
    stack = [(0, 0)]  # [(left, height)]
    for w in range(W + 1):
        if dp[h][w] >= stack[-1][1]:  # まだ長方形が決定されないとき
            stack.append((w, dp[h][w]))
        else:  # 高さが足りずに長方形が決定されるとき
            while stack[-1][1] > dp[h][w]:  # stack[0] = (0, 0) なので、 stack[0]は絶対に取り出されない
                left_pos, height = stack.pop()
                area = height * (w - left_pos)  # 長方形の面積
                ans = max(ans, area)
            stack.append((left_pos, dp[h][w]))

print(ans)

Submission status: Accepted

Solution code:

"""
Writer: SPD_9X2
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_3_B&lang=ja

各セルに対して、上にいくつ0が連続しているか数えれば、
ヒストグラム上での最大長方形問題になる
"""


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*(i-np))

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

    return ans

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

c = []
for i in range(H):
    C = list(map(int,input().split()))
    c.append(C)

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

        if c[i][j] == 1:
            continue
        elif i == 0:
            zlis[i][j] = 1
        else:
            zlis[i][j] = zlis[i-1][j] + 1

#print (zlis)
ans = 0
for i in range(H):
    ans = max(ans , Largest_rectangle_in_histgram(zlis[i]))

print (ans)

Submission status: Accepted

Solution code:
# n,m = map(int,sys.stdin.readline().split())
# a = list(map(int,sys.stdin.readline().split()))
# s = sys.stdin.readline().rstrip()
import sys,bisect
sys.setrecursionlimit(15000)
h,w = map(int,sys.stdin.readline().split())
buffer = [None for _ in range(h)]
T = [[0]*(w+1) for _ in range(h)]

for r in range(h):
  buffer[r] = list(map(int,sys.stdin.readline().split()))

for col in range(w):
  for r in range(h):
    if buffer[r][col] == 1:
      T[r][col] = 0
    elif r == 0:
      T[0][col] = 1
    else:
      T[r][col] = T[r-1][col]+1
m = 0

for buffer in T:
  stack = []
  for i in range(w+1):
    rect = {"h":buffer[i],"p":i}
    if not stack:
      stack.append(rect)
    else:
      if stack[-1]["h"] < buffer[i]:
        stack.append(rect)
      elif stack[-1]["h"] > buffer[i]:
        while stack and stack[-1]["h"] >= buffer[i]:
          pre = stack.pop()
          m = max(m,pre["h"]*(i-pre["p"]))
          rect["p"] = pre["p"]
        stack.append(rect)
print(m)

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
C=[list(map(int,input().split())) for _ in range(h)]
DP=[[0 for _ in range(w)] for _ in range(h)]

for i in range(w):
    if C[0][i]==0:DP[0][i]=1
    else:DP[0][i]=0

for i in range(1,h):
    for j in range(w):
        if C[i][j]==0:DP[i][j]=DP[i-1][j]+1
        else:DP[i][j]=0

cost=0
for i in range(h):
    stack=[]
    for j in range(w):
        if len(stack)==0:
            stack.append((DP[i][j],j))
        elif DP[i][j]>stack[-1][0]:
            stack.append((DP[i][j],j))
        elif DP[i][j]<stack[-1][0]:
            add=0
            while DP[i][j]<stack[-1][0]:
                rect,pos=stack.pop()
                cost=max(cost,(j-pos)*rect)
                add=pos
                if len(stack)==0:break
            stack.append((DP[i][j],add))

    if len(stack)!=0:
        while len(stack)!=0:
            rect,pos=stack.pop()
            cost=max(cost,(w-pos)*rect)

print(cost)

Submission status: Accepted

Solution code:
#!python3

from collections import deque

iim = lambda: map(int, input().rstrip().split())

def calc(dp):
    ans = 0
    dq = deque([[0, 0]])
    #print(dp)
    for i, hi in enumerate(dp):
        j = i
        while dq[-1][1] > hi:
            j, h1 = dq.pop()
            ans = max(ans, (i - j) * h1)

        if dq[-1][1] < hi:
            dq.append([j, hi])

    i = len(dp)
    for j, hi in dq:
        ans = max(ans, (i - j) * hi)
    #print(i, dq, ans)
    return ans

def resolve():
    H, W = iim()

    dp = [0] * W
    dp0 = dp[:]
    ans = 0
    for i in range(H):
        C = list(iim())

        for i, ci in enumerate(C):
            dp[i] = 0 if ci else dp0[i] + 1

        ans = max(ans, calc(dp))
        dp, dp0 = dp0, dp

    print(ans)

if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
def calc_largest_rect_in_hist(heights):
    heights.append(0)
    stack = []
    left = [0] * len(heights)
    ans = 0
    for i, height in enumerate(heights):
        while stack and heights[stack[-1]] >= height:
            idx = stack.pop()
            ans = max(ans, (i - left[idx] - 1) * heights[idx])
        left[i] = stack[-1] if stack else -1
        stack.append(i)
    heights.pop()
    return ans


def aoj_hist():
    # https://onlinejudge.u-aizu.ac.jp/courses/library/7/DPL/all/DPL_3_C
    input()
    print(calc_largest_rect_in_hist([int(x) for x in input().split()]))


def aoj_rect():
    # https://onlinejudge.u-aizu.ac.jp/courses/library/7/DPL/all/DPL_3_B
    H, W = map(int, input().split())
    board = [[int(x) for x in input().split()] for _ in range(H)]
    dp = [0] * W
    ret = 0
    for r in range(H):
        for c in range(W):
            dp[c] = dp[c] + 1 if board[r][c] == 0 else 0
        ret = max(ret, calc_largest_rect_in_hist(dp))
    print(ret)


if __name__ == "__main__":
    # aoj_hist()
    aoj_rect()

Submission status: Accepted

Solution code:



class Rectangle:
    def __init__(self, height, position):
        self.height = height
        self.position = position

def getLargestRectangleRow(size, bufTmp):
    S = []
    maxv = 0
    #bufTmp[0] * size
    bufTmp.append(0)
    for i in range(size + 1):
        rect = Rectangle(bufTmp[i], i)
        
        if len(S) == 0:
            S.append(rect)
        else:
            if S[-1].height < rect.height:
                S.append(rect)
            elif S[-1].height > rect.height:
                target = i
                while len(S) >= 1 and S[-1].height >= rect.height:
                    pre = S.pop()
                    area = pre.height * (i-pre.position)
                    maxv = max(maxv, area)
                    target = pre.position
                rect.position = target
                S.append(rect)
    return maxv


def getLargestRectangle():
    for j in range(W):
        for i in range(H):
            if buf[i][j]:
                T[i][j] = 0
            else:
                if i > 0:
                    T[i][j] = T[i-1][j] + 1
                else:
                    T[i][j] = 1
    maxv = 0
    for i in range(H):
        maxv = max(maxv, getLargestRectangleRow(W, T[i]))

    return maxv


nums=list(map(int,input().split()))
H = nums[0]
W = nums[1]
buf = [[0 for i in range(W)] for j in range(H)]
T = [[0 for i in range(W)] for j in range(H)]
for i in range(H):
    nums=list(map(int,input().split()))
    for j in range(W):
        buf[i][j] = nums[j]

print(getLargestRectangle())

Submission status: Accepted

Solution code:
# https://onlinejudge.u-aizu.ac.jp/courses/library/7/DPL/all/DPL_3_B
# この問題は前処理パートと、効率よく長方形の面積を求めるパートに分かれる。

from itertools import product, chain

# load data
H, W = list(map(int, input().split()))
C = []
for i in range(H):
    C.append(list(map(int, input().split())))


# まず、前処理を行う
# T (H,W) ... そのマスより上に何マスまで濡れるか
T = []
pre_tmp = [0] * W
for c in C:
    tmp = []
    for cc, pre in zip(c, pre_tmp):
        if cc == 1:
            tmp.append(0)
        else:
            tmp.append(pre + 1)
    T.append(tmp)
    pre_tmp = tmp.copy()


def get_largest_rectangle(hist: list):
    '''
    ヒストグラムが渡されたときに、その中の最大の長方形を返す
    '''
    hist = hist.copy()
    hist.append(0)
    ret = 0
    stack = []
    for i, v in enumerate(hist):
        # vが本で言うrectのこと
        if len(stack) == 0:
            stack.append((i, v))
        elif stack[-1][1] < v:
            stack.append((i, v))
        elif stack[-1][1] > v:
            while stack and stack[-1][1] > v:
                # スタックが空でなく、最後の要素がvより大きい限りは、
                # 面積の最大値を更新していく
                i_left, h = stack.pop()
                ret = max(ret, (i - i_left) * h)
            stack.append((i_left, v))
    return ret


# 各行について走査することで長方形の最大値を求める
ans = 0
for t in T:
    ans = max(ans, get_largest_rectangle(t))
print(ans)

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
C=[list(map(int,input().split())) for i in range(h)]

def Largest_Rectangle(grid,h,w):
    re=0
    hist=[[0]*(w+1) for i in range(h)]
    for j in range(w):
        if C[0][j]==0:
            hist[0][j]=1
    for j in range(w):
        for i in range(1,h):
            if C[i][j]==1:continue
            hist[i][j]=hist[i-1][j]+1
    for i in range(h):
        re=max(re,stack_processing_of_rectangle(hist[i]))
    return re

def stack_processing_of_rectangle(hist):
    # スタック処理
    maxrect=0
    stack=[]
    for j in range(w+1):
        if not stack:
            stack.append((hist[j],j))
        elif stack[-1][0]<hist[j]:
            stack.append((hist[j],j))
        elif stack[-1][0]>hist[j]:
            while stack and stack[-1][0]>hist[j]:
                hi,wi=stack.pop()
                maxrect=max(maxrect,hi*(j-wi))
            stack.append((hist[j],wi))
    return maxrect

print(Largest_Rectangle(C,h,w))
# hist=[[0]*(w+1) for i in range(h)]
# for j in range(w):
#     if C[0][j]==0:
#         hist[0][j]=1
# for j in range(w):
#     for i in range(1,h):
#         if C[i][j]==1:continue
#         hist[i][j]=hist[i-1][j]+1

# # スタック処理
# maxrect=0
# stack=[]
# for i in range(h):
#     for j in range(w+1):
#         if not stack:
#             stack.append((hist[i][j],j))
#         elif stack[-1][0]<hist[i][j]:
#             stack.append((hist[i][j],j))
#         elif  stack[-1][0]==hist[i][j]:
#             pass
#         elif stack[-1][0]>hist[i][j]:
#             while stack and stack[-1][0]>hist[i][j]:
#                 hi,wi=stack.pop()
#                 maxrect=max(maxrect,hi*(j-wi))
#             stack.append((hist[i][j],wi))
# print(maxrect)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()

def max_rect_in_hist(Hist):
    Hist.append(0)
    ans=0
    Q=[(-1,0)]
    for i,h in enumerate(Hist):
        while(Q[-1][1]>h):
            i0,h0=Q.pop()
            ans=max(ans,h0*(i-Q[-1][0]-1))
        if(Q[-1][1]<=h):
            Q.append((i,h))
    return ans

def resolve():
    h,w=map(int,input().split())
    C=[list(map(lambda x:1-int(x),input().split())) for _ in range(h)]
    from itertools import product
    for i,j in product(range(h-1),range(w)):
        if(C[i+1][j]): C[i+1][j]+=C[i][j]
    print(max(max_rect_in_hist(c) for c in C))
resolve()

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
height = W * [0]
max_area = 0
for _ in range(H):
    height = [0 if t else height[j]+1 for j, t in enumerate(map(int, input().split()))]
    height.append(0)
    stack = []
    for i, h in enumerate(height):
        if stack:
            if stack[-1][1] == h:
                continue
            elif stack[-1][1] > h:
                while stack and (stack[-1][1] >= h):
                    i_stack, h_stack = stack.pop()
                    max_area = max(max_area, (i - i_stack) * (h_stack))
                i = i_stack
                
            
        stack.append((i, h))
        
print(max_area)

Submission status: Accepted

Solution code:
# スタックの実装。
class Stack():
    def __init__(self):
        self.stack = []
    # データを追加する。
    def push(self, item):
        self.stack.append(item)
    # データを取り出す。
    def pop(self):
        return self.stack.pop()
    # スタックの中身を確認する。
    def get_stack(self):
        return self.stack
    # スタックが空ならばTrueを返す。
    def isEmpty(self):
        return len(self.stack) == 0
    # スタックに格納されているものの数を返す。
    def count(self):
        return len(self.stack)
    #　スタックのトップを見る（取り出さずに）。
    def top(self):
        return self.stack[-1]

# ヒストグラムの最大長方形を求める関数。
def Histogram(n,l):
    if n == 0:
        return 0
    stack = Stack()
    t = 0
    ans = 0
    while t < n:
        r = l[t]
        if stack.isEmpty():
            stack.push((r,t))
            t += 1
            # print(stack.get_stack(),t)
        elif stack.top()[0] < r:
            stack.push((r,t))
            t += 1
            # print(stack.get_stack(),t)
        elif stack.top()[0] == r:
            t += 1
            # print(stack.get_stack(),t)
        elif stack.top()[0] > r:
            while stack.top()[0] > r:
                p,q = stack.pop()
                ans = max(ans,p*(t-q))
                # print(stack.get_stack(),t)
                if stack.isEmpty():
                    break;
            stack.push((r,q))
            t += 1
    while not stack.isEmpty():
        p,q = stack.pop()
        ans = max(ans, p*(t-q))
        # print(stack.get_stack(),t)
    return ans


H,W  = [int(_) for _ in input().split()]
dp = [[0]*W for _ in range(H)]
for i in range(H):
    for j,value in enumerate([int(_) for _ in input().split()]):
        dp[i][j] = value
c = 1
for j in range(W):
    i = 0
    while i < H:
        if dp[i][j] == 0:
            dp[i][j] = c
            c += 1
        else:
            dp[i][j] = 0
            c = 1
        i += 1
    c = 1

# for i in range(H):
#     print(dp[i])

ans = 0
l = []
for i in range(H):
    for j in range(W):
        if dp[i][j] == 0:
            ans = max(ans,Histogram(len(l),l))
            # print(len(l),l)
            l = []
        else:
            l.append(dp[i][j])
    ans = max(ans,Histogram(len(l),l))
    # print(len(l),l)
    l = []
print(ans)


# print('TEST')
# print(Histogram(5, [3,5,4,5,5]))