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 pprint import PrettyPrinter

pp = PrettyPrinter()


def read_tiles(h, w):
    c = []
    for _ in range(h):
        c.append([int(x) for x in input().split()])
    return c


def make_histogram(h, w, c):
    hg = [[None] * w for _ in range(h)]
    for j in range(w):
        hg[0][j] = 1 if c[0][j] == 0 else 0
    for i in range(1, h):
        for j in range(w):
            hg[i][j] = hg[i - 1][j] + 1 if c[i][j] == 0 else 0
    return hg


def largest_rectangle(h, w, c):
    lr = 0
    hg = make_histogram(h, w, c)
    # pp.pprint(hg)
    s = []
    for i in range(h):
        hg[i] += [0]
        for j in range(w + 1):
            if len(s) == 0:
                if hg[i][j] > 0:
                    s.append((hg[i][j], j))
            else:
                top = s[-1]
                if top[0] < hg[i][j]:
                    s.append((hg[i][j], j))
                elif hg[i][j] == top[0]:
                    pass
                else:
                    while len(s) > 0 and s[-1][0] >= hg[i][j]:
                        top = s.pop()
                        lr = max(lr, top[0] * (j - top[1]))
                    s.append((hg[i][j], top[1]))
            # print(j, lr, s)
    return lr


def main():
    h, w = map(int, input().split())
    c = read_tiles(h, w)
    print(largest_rectangle(h, w, c))


main()

Submission status: Accepted

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

c=[[0 for _ in range(w)]]
DP = [[0 for _ in range(w+1)] for __ in range(h+1)]
for _ in range(h):
    c_tmp = list(map(int, input().split( )))
    c.append(c_tmp)


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

#for i in range(1,h+1):
#    print(*DP[i])
S = []
ans = []
Tst =  [[0 for _ in range(w)] for __ in range(h+1)]
for j in range(1,h+1):
    #S = []
    for i in range(w+1):
        if len(S) > 0:
            if S[-1][0] <= DP[j][i]:
                S.append([DP[j][i],1])
            
            else:#if S[-1] > DP[j][i]:
                tmp = 0
                while len(S) > 0 and S[-1][0] > DP[j][i]:
                    pp = S.pop()
                    tmp += pp[1]
                    ans.append(pp[0]*tmp)
                    Tst[j][i-1] = pp[0]*tmp
                S.append([DP[j][i],tmp+1])
                
        else:
            S.append([DP[j][i],1])
#print()
#for i in range(1,h+1):
#    print(*Tst[i])
#print()
try:
    print(max(ans))
except:
    print(0)

Submission status: Accepted

Solution code:
from typing import List, Tuple


def rectangle(max_width: int, hist: List[int]) -> int:
    stack: List[Tuple[int, int]] = []  # (height, x_position)
    ans = 0
    for i, h in enumerate(hist):
        j = i
        while stack and stack[-1][0] > h:
            pre_h, j = stack.pop()
            ans = max(ans, (i - j) * pre_h)

        if not stack or stack[-1][0] < h:
            stack.append((h, j))

    ans = max(ans, max((max_width - j) * h for h, j in stack))
    return ans


if __name__ == "__main__":
    H, W = map(lambda x: int(x), input().split())
    hist = [0] * W

    result = 0
    for _ in range(H):
        one_row = list(map(int, input().split()))
        hist = list(map(lambda pre, cur: (pre + 1) * (cur ^ 1), hist, one_row))
        result = max(result, rectangle(W, hist))

    print(result)

Submission status: Accepted

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

import sys
from collections import deque

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

H,W=MAP()
grid=[None]*H
for i in range(H):
    grid[i]=LIST()

# その行を底辺として、高さをどこまで伸ばせるか記録しておく
acc=list2d(H, W, 0)
for j in range(W):
    if grid[0][j]!=1:
        acc[0][j]=1
for j in range(W):
    for i in range(1, H):
        if grid[i][j]!=1:
            acc[i][j]=acc[i-1][j]+1
# 最後にスタックに残ってる分を確認するために番兵的に足す
for i in range(H):
    acc[i].append(0)

mx=0
# 各行を高さのヒストグラムとみなす
for i, hist in enumerate(acc):
    stack=deque()
    for j, h in enumerate(hist):
        if not len(stack):
            stack.append((j, h))
        else:
            if stack[-1][1]<h:
                stack.append((j, h))
            elif stack[-1][1]>h:
                # 次のhがスタックより低かったら、そこより手前の最大を確定する
                while len(stack) and stack[-1][1]>h:
                    prev=stack.pop()
                    w2=j-prev[0]
                    h2=prev[1]
                    mx=max(mx, h2*w2)
                stack.append((prev[0], h))
print(mx)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Pattern - Largest Rectangle
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_3_B&lang=jp

"""
import sys


def solve(H, W, grid):
    def calc_hist(m):
        ans = [[0] * W for _ in range(H)]
        for y, row in enumerate(m):
            for x, ch in enumerate(row):
                if ch == '0':
                    ans[y][x] = ans[y - 1][x] + 1 if y > 0 else 1
        return ans

    def calc_area(hist):
        stack = []
        area, left = 0, 0
        for x, h in enumerate(hist):
            if not stack or stack[-1][0] < h:
                stack.append((h, x))
            elif stack[-1][0] > h:
                while stack and stack[-1][0] >= h:
                    hh, left = stack.pop()
                    area = max(area, hh*(x-left))
                stack.append((h, left))
        return area

    hist = calc_hist(grid)
    ans = 0
    for y in range(H):
        ans = max(ans, calc_area(hist[y]+[0]))
    return ans


def main(args):
    H, W = map(int, input().split())
    grid = [input().replace(' ', '') for _ in range(H)]
    ans = solve(H, W, grid)
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Accepted

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

# 上方向に連続するタイルの数を記録する
t = []
for _ in range(H+2):
    t.append([0]*(W+2))

for w in range(1, W+1):
    for h in range(1, H+1):
        if c[h-1][w-1] == 1:
            t[h][w] = 0
        else:
            t[h][w] = t[h-1][w]+1

ans = 0
for h in range(1, H+1):
    s = []
    for w in range(1, W+2):
        if len(s) == 0 or s[-1][0] < t[h][w]:
            s.append([t[h][w], w])
        elif s[-1][0] > t[h][w]:
            li = w
            while len(s) > 0 and s[-1][0] >= t[h][w]:
                r = s.pop(-1)
                tmp = (w-r[1])*r[0]
                if tmp > ans:
                    ans = tmp
                li = r[1]
            s.append([t[h][w], li])
print(ans)

Submission status: Accepted

Solution code:
def rectangle(n, hs):
  stack = [] #高さと位置を格納
  ans = 0
  for i, h in enumerate(hs):
    j = i
    while stack and stack[-1][0] > h:
      pre_h, j = stack.pop()
      ans = max(ans, (i - j) * pre_h)

    if not stack or stack[-1][0] < h:
      stack.append((h, j))

  ans = max(ans, max((n-j) * h2 for h2, j in stack))

  return ans

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

#ここでリストを固定化しておかないと値を受け付けてくれない
hist = [0] * W
result = 0
for _ in range(H):
  ht = list(map(int, input().split()))
  hist = list(map(lambda pre, cur: (pre+1) * (cur ^ 1), hist, ht))
  result = max(result, rectangle(W, hist))
print(result)

Submission status: Accepted

Solution code:


def rectangle(n, hs):
    stack = []  # (height, pos) 高さと位置が格納される
    ans = 0
    for i, h in enumerate(hs):
        j = i
        while stack and stack[-1][0] > h:
            pre_h, j = stack.pop()
            ans = max(ans, (i - j) * pre_h)

        if not stack or stack[-1][0] < h:
            stack.append((h, j))

    ans = max(ans, max((n - j) * h2 for h2, j in stack))

    return ans


H, W = map(int, input().split())
hist = [0] * W
result = 0
for _ in range(H):
    ht = list(map(int, input().split()))
    hist = list(map(lambda pre, cur: (pre + 1) * (cur ^ 1), hist, ht))
    result = max(result, rectangle(W, hist))

print(result)

Submission status: Accepted

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


def getLargestRectangleInRow(size, buffer):
    s = []
    maxv = 0
    buffer.append(0)
    for i in range(size + 1):
        rect = Rectangle(buffer[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) != 0 and s[-1].height >= rect.height:
                    pre = s.pop()
                    area = pre.height * (i - pre.pos)
                    maxv = max(maxv, area)
                    target = pre.pos
                rect.pos = target
                s.append(rect)

    return maxv


def getLargestRectangle(H, W, buffer):
    t = [[0] * W for i in range(H)]
    for i in range(H):
        for j in range(W):
            if buffer[i][j] == 1:
                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, getLargestRectangleInRow(W, t[i]))
    return maxv



if __name__ == '__main__':
    h, w = [int(v) for v in input().split()]
    c = []
    for i in range(h):
        c.append([int(v) for v in input().split()])

    print(getLargestRectangle(h, w, c))

Submission status: Runtime Error

Solution code:
def new_max_rectangle(array):
    max_area = 0

    for i in range(len(array)):
        min_height = array[i]
        width = 1
        for j in range(i, len(array)):
            if array[j] == 0:
                width = 1
                if j <= i:
                    min_height = array[j + 1]
                continue
            min_height = array[j] if min_height > array[j] else min_height
            max_area = width * min_height if width * min_height > max_area else max_area
            width += 1

    return max_area


def algorithm():
    r, c = map(int, input().split(' '))

    ans_array = [0 for _ in range(c)]
    input_matrix = []

    for _ in range(r):
        input_matrix.append(list(map(int, input().split(' '))))

    largest_square = 0

    for i in range(r):
        for j in range(c):
            ans_array[j] = ans_array[j] + 1 if input_matrix[i][j] == 0 else 0
        m = new_max_rectangle(ans_array)
        largest_square = largest_square if largest_square > m else m

    print(largest_square)


def main():
    algorithm()


if __name__ == '__main__':
    main()