Problem:
Largest Rectangle Given a matrix ( H × W ) which contains only 1 and 0, find the area of the largest rectangle which only contains 0s. Input  H  W  c 1,1  c 1,2 ... c 1,W  c 2,1  c 2,2 ... c 2,W : c H,1  c H,2 ... c H,W  In the first line, two integers H and W separated by a space character are given. In the following H lines, c i , j , elements of the H × 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

Solution (Python):
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)

Solution (Python):
h, w = map(int, raw_input().split())
c = [map(int, raw_input().split()) for i in xrange(h)]
cnt = [[0]*w for i in xrange(h)]

for j in xrange(w):
    seq = 0
    for i in xrange(h):
        if c[i][j] == 0:
            seq += 1
        else:
            seq = 0
        cnt[i][j] = seq
ans = 0
st = [(0, -1)]
for i in xrange(h):
    for j in xrange(w):
        v = cnt[i][j]
        last = j
        while v < st[-1][0]:
            l, k = st.pop()
            last = k
            ans = max(ans, l*(j-k))
        if st[-1][0] < v:
            st.append((v, last))
    while 0 < st[-1][0]:
        l, k = st.pop()
        ans = max(ans, l*(w-k))
print ans

Solution (Python):
h, w = map(int, input().split())
max_rect, prev = 0, [0] * (w + 1)
for i in range(h):
    current = [p + 1 if f else 0 for f, p in zip(map(lambda x: int(x) ^ 1, input().split()), prev)] + [0]
    stack = [(0, 0)]
    for j in range(w + 1):
        c_j = current[j]
        if stack[-1][0] < c_j:
            stack.append((c_j, j))
            continue
        if stack[-1][0] > c_j:
            since = 0
            while stack[-1][0] > c_j:
                height, since = stack.pop()
                max_rect = max(max_rect, height * (j - since))
            if c_j:
                stack.append((c_j, since))
    prev = current
print(max_rect)

Solution (Python):



"""
input:
4 5
0 0 1 0 0
1 0 0 0 0
0 0 0 1 0
0 0 0 1 0

output:
6
"""

import sys





class Rectangle(object):
    __slots__ = ('pos', 'height')

    def __init__(self, pos=float('inf'), height=-1):
        """
        init a Rectangle
        """
        self.pos = pos
        self.height = height


def gen_rec_info(_carpet_info):
    dp = [[float('inf')] * W for _ in range(H)]

    for i in range(H):
        for j in range(W):
            if int(_carpet_info[i][j]):
                dp[i][j] = 0
            else:
                dp[i][j] = dp[i - 1][j] + 1 if i > 0 else 1

    return dp


def get_largest_area(_hi_info):
    hi_max_area = 0
    rec_stack = []
    _hi_info.append(0)

    for i, v in enumerate(_hi_info):
        rect = Rectangle(pos=i, height=int(v))
        if not rec_stack:
            rec_stack.append(rect)
        else:
            last_height = rec_stack[-1].height
            if last_height < rect.height:
                rec_stack.append(rect)
            elif last_height > rect.height:
                target = i
                while rec_stack and rec_stack[-1].height >= rect.height:
                    pre = rec_stack.pop()
                    area = pre.height * (i - pre.pos)
                    hi_max_area = max(hi_max_area, area)
                    target = pre.pos
                rect.pos = target
                rec_stack.append(rect)

    return hi_max_area


def solve(_rec_info):
    overall_max_area = 0
    for hi_info in _rec_info:
        overall_max_area = max(overall_max_area, get_largest_area(hi_info))

    return overall_max_area


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    H, W = map(int, _input[0].split())
    carpet_info = list(map(lambda x: x.split(), _input[1:]))
    

    rec_info = gen_rec_info(carpet_info)
    
    ans = solve(rec_info)
    print(ans)

Solution (Python):



"""
input:
4 5
0 0 1 0 0
1 0 0 0 0
0 0 0 1 0
0 0 0 1 0

output:
6
"""

import sys


class Rectangle(object):
    __slots__ = ('pos', 'height')

    def __init__(self, pos=float('inf'), height=-1):
        """
        init a Rectangle
        """
        self.pos = pos
        self.height = height


def gen_rec_info(_carpet_info):
    dp = [[float('inf')] * W for _ in range(H)]

    for i in range(H):
        for j in range(W):
            if int(_carpet_info[i][j]):
                dp[i][j] = 0
            else:
                dp[i][j] = dp[i - 1][j] + 1 if i else 1

    return dp


def get_largest_area(_hi_info):
    hi_max_area = 0
    rec_stack = []
    _hi_info.append(0)

    for i, v in enumerate(_hi_info):
        rect = Rectangle(pos=i, height=int(v))
        if not rec_stack:
            rec_stack.append(rect)
        else:
            last_height = rec_stack[-1].height
            if last_height < rect.height:
                rec_stack.append(rect)
            elif last_height > rect.height:
                target = i
                while rec_stack and rec_stack[-1].height >= rect.height:
                    pre = rec_stack.pop()
                    area = pre.height * (i - pre.pos)
                    hi_max_area = max(hi_max_area, area)
                    target = pre.pos
                rect.pos = target
                rec_stack.append(rect)

    return hi_max_area


def solve(_rec_info):
    overall_max_area = 0
    for hi_info in _rec_info:
        overall_max_area = max(overall_max_area, get_largest_area(hi_info))

    return overall_max_area


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    H, W = map(int, _input[0].split())
    carpet_info = list(map(lambda x: x.split(), _input[1:]))

    rec_info = gen_rec_info(carpet_info)
    
    ans = solve(rec_info)
    print(ans)

Solution (Python):



"""
input:
4 5
0 0 1 0 0
1 0 0 0 0
0 0 0 1 0
0 0 0 1 0

output:
6
"""

import sys


class Rectangle(object):
    __slots__ = ('pos', 'height')

    def __init__(self, pos=float('inf'), height=-1):
        """
        init a Rectangle
        """
        self.pos = pos
        self.height = height


def gen_rec_info(_carpet_info):
    dp = [[float('inf')] * W for _ in range(H)]

    for i in range(H):
        for j in range(W):
            if int(_carpet_info[i][j]):
                dp[i][j] = 0
            else:
                dp[i][j] = dp[i - 1][j] + 1 if i else 1

    return dp


def get_largest_area(_hi_info):
    hi_max_area = 0
    rec_stack = []
    _hi_info.append(0)

    for i, v in enumerate(_hi_info):
        rect = Rectangle(pos=i, height=int(v))
        if not rec_stack:
            rec_stack.append(rect)
        else:
            last_height = rec_stack[-1].height
            if last_height < rect.height:
                rec_stack.append(rect)
            elif last_height > rect.height:
                target = i
                while rec_stack and rec_stack[-1].height >= rect.height:
                    pre = rec_stack.pop()
                    area = pre.height * (i - pre.pos)
                    hi_max_area = max(hi_max_area, area)
                    target = pre.pos
                rect.pos = target
                rec_stack.append(rect)

    return hi_max_area


def solve(_rec_info):
    overall_max_area = 0
    for hi_info in _rec_info:
        overall_max_area = max(overall_max_area, get_largest_area(hi_info))

    return overall_max_area


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    H, W = map(int, _input[0].split())
    carpet_info = list(map(lambda x: x.split(), _input[1:]))

    rec_info = gen_rec_info(carpet_info)
    
    ans = solve(rec_info)
    print(ans)

Solution (Python):



"""
input:
4 5
0 0 1 0 0
1 0 0 0 0
0 0 0 1 0
0 0 0 1 0

output:
6
"""

import sys


class Rectangle(object):
    __slots__ = ('pos', 'height')

    def __init__(self, pos=float('inf'), height=-1):
        """
        init a Rectangle
        """
        self.pos = pos
        self.height = height


def gen_rec_info(_carpet_info):
    dp = [[float('inf')] * W for _ in range(H)]

    for i in range(H):
        for j in range(W):
            if int(_carpet_info[i][j]):
                dp[i][j] = 0
            else:
                dp[i][j] = dp[i - 1][j] + 1 if i else 1

    return dp


def get_largest_area(_hi_info):
    hi_max_area = 0
    rec_stack = []
    _hi_info.append(0)

    for i, v in enumerate(_hi_info):
        rect = Rectangle(pos=i, height=int(v))
        if not rec_stack:
            rec_stack.append(rect)
        else:
            last_height = rec_stack[-1].height
            if last_height < rect.height:
                rec_stack.append(rect)
            elif last_height > rect.height:
                target = i
                while rec_stack and rec_stack[-1].height >= rect.height:
                    pre = rec_stack.pop()
                    area = pre.height * (i - pre.pos)
                    hi_max_area = max(hi_max_area, area)
                    target = pre.pos
                rect.pos = target
                rec_stack.append(rect)

    return hi_max_area


def solve(_rec_info):
    overall_max_area = 0
    for hi_info in _rec_info:
        overall_max_area = max(overall_max_area, get_largest_area(hi_info))

    return overall_max_area


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    H, W = map(int, _input[0].split())
    carpet_info = list(map(lambda x: x.split(), _input[1:]))

    rec_info = gen_rec_info(carpet_info)
    
    ans = solve(rec_info)
    print(ans)

Solution (Python):
import sys, collections

def solve():
    file_input = sys.stdin
    H, W = map(int, file_input.readline().split())
    max_area = 0
    prev = [0] * W
    rect_stack = collections.deque()
    for line in file_input:
        tile_line = map(int, line.split())
        for i, tpl in enumerate(zip(tile_line, prev)):
            t, p = tpl
            if t:
                h = 0
                prev[i] = 0
            else:
                h = p + 1
                prev[i] = h
            if (not rect_stack) or (h > rect_stack[-1][0]):
                rect_stack.append((h, i))
            elif h < rect_stack[-1][0]:
                while rect_stack:
                    if rect_stack[-1][0] >= h:
                        rect_h, rect_i = rect_stack.pop()
                        max_area = max(max_area, rect_h * (i - rect_i))
                    else:
                        break
                rect_stack.append((h, rect_i))
        while rect_stack:
            rect_h, rect_i = rect_stack.pop()
            max_area = max(max_area, rect_h * (W - rect_i))
    print(max_area)

solve()

Solution (Python):
import sys, collections
file = sys.stdin
H,W = map(int, file.readline().split())
C = [list(map(int,i.split())) for i in file.readlines()]
prev = [0 for i in range(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 = []
    L = collections.deque()
    for i,v in enumerate(P):
        if not L:
            L.append((i, v))
            continue
        if 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))
    while L:
        a = L.pop()
        G.append((len(P) - a[0]) * a[1])
    return max(G)

def ans(C):
    ans = []
    for i in range(H):
        currentC = C[:i+1]
        ans.append(square(currentC))
    return str(max(ans))
print(ans(C))

Solution (Python):
import sys, collections, heapq
file = sys.stdin
H,W = map(int, file.readline().split())
C = [list(map(int,i.split())) for i in file.readlines()]
prev = [0 for i in range(W)]
G = []
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)
    global G
    L = collections.deque()
    for i,v in enumerate(P):
        if not L:
            L.append((i, v))
            continue
        if 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()
                heapq.heappush(G,  -(k - a[0] + 1) * a[1])
            L.append((a[0], v))
    while L:
        a = L.pop()
        heapq.heappush(G, -(len(P) - a[0]) * a[1])

def ans(C):
    ans = []
    global G
    for i in range(H):
        currentC = C[:i+1]
        square(currentC)
    return str(-G[0])

print(ans(C))

Solution (Python):
def judge(n,hs):

    stack = []
    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,input().split())
hs = [0]*W
result = 0
for i in range(H):
    f = lambda x,y:(x+1)*abs(y-1)

    ht = list(map(int, input().split()))
    hs = list(map(f,hs,ht))

    result = max(result,judge(W,hs))

print(result)

Solution (Python):
from sys import stdin
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 = []
    L = []
    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)]))

Solution (Python):
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)]))

Solution (Python):
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)]))

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):

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 = [] 
    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)

Solution (Python):
from collections import deque

def rectangle(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, 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)

Solution (Python):

'''
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())))


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)
            
        else:
            if S[-1].height < rect.height:
                S.append(rect)
                
            elif S[-1].height > rect.height:
                target = w
                while len(S) > 0 and S[-1].height >= rect.height:
                    
                    pre = S.pop()
                    area = pre.height * (w - pre.pos)
                    maxv = max(maxv, area)
                    target = pre.pos
                rect.pos = target
                S.append(rect)
    return maxv



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


print(ans)

Solution (Python):


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)

Solution (Python):
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 - 1, -1, -1):
  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))
        if not stack:
          stack.append((score, last_ind))
        elif stack[-1][0] == score:
          pass
        else:
          stack.append((score, last_ind))

print(ans)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
import sys

import math
import collections

import bisect
import itertools
import fractions

import copy

import decimal

import queue



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


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




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

    for i in range(len(heights)):
        
        
        
        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)

    
    
    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
        
        ans = max(ans, largestRectangInHistgram(current))

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
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)

Solution (Python):

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()

Solution (Python):
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)

Solution (Python):

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 = [[0] * (W + 1) for _ in range(H)]
for h in range(H):
    for w in range(W + 1):  
        if w == W:
            dp[h][w] = 0
            continue
        if C[h][w] == 1:
           dp[h][w] = 0
        elif h == 0:  
           dp[0][w] = 1
        else:
           dp[h][w] = dp[h-1][w] + 1


ans = 0
for h in range(H):
    stack = [(0, 0)]  
    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]:  
                left_pos, height = stack.pop()
                area = height * (w - left_pos)  
                ans = max(ans, area)
            stack.append((left_pos, dp[h][w]))

print(ans)

Solution (Python):

"""
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


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

print (ans)