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: Wrong Answer

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

    for i in range(1, max(array) + 1):
        mini_height = 99999
        count = 0
        for j in range(i, max(array) + 1):
            if array[j] == 0:
                if j == i:
                    mini_height = array[j]
                break
            else:
                mini_height = mini_height if array[j] > mini_height else array[j]
                count += 1

        max_area = count * mini_height if count * mini_height > max_area else max_area

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

Submission status: Wrong Answer

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 + 1, len(array)):
            width += 1
            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

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

Submission status: Wrong Answer

Solution code:
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:
            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, j))
    prev = current

print(max_rect)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

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


# from collections import namedtuple


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 = [[0] * (W + 1) for _ in range(H + 1)]

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

    return dp


def get_largest_area(_hi_info):
    hi_max_area = 0
    rec_stack = []
    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)
                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:]))
    # Rectangle = namedtuple('Rectangle', ('pos', 'height'))

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

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

"""
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 * (target - 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)
    # print(rec_info)
    ans = solve(rec_info)
    print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

"""
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 = [[1] * (W + 1) for _ in range(H + 1)]

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

    return dp


def get_largest_area(_hi_info):
    hi_max_area = 0
    rec_stack = []
    _hi_info[-1] = 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)
    # print(rec_info)
    ans = solve(rec_info)
    print(ans)

Submission status: Wrong Answer

Solution code:
import sys
file = sys.stdin
H,W = map(int, file.readline().split())
C1 = [list(map(int,i.split())) for i in file.readlines()]
C2 = [i[::-1] for i in C1[::-1]]

def height(C):
    P = []
    for i in range(W):
        p = 0
        for j in range(H):
            if C[j][i] == 1:
                p = 0
            else: p += 1
        P.append(p)
    return P

def square(C):
    P = height(C)
    G = []
    L = []
    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 = L[-1][0]
            while L and v < L[-1][1]:
                a = L.pop()
                G.append((k - a[0] + 1) * a[1])
            L.append((i, v))
    while L:
        a = L.pop()
        G.append((len(P) - a[0]) * a[1])
    return max(G)

def ans(C1, C2):
    return str(max(square(C1), square(C2)))

print(ans(C1, C2))

Submission status: Wrong Answer

Solution code:
import sys
file = sys.stdin
H,W = map(int, file.readline().split())
C = [list(map(int,i.split())) for i in file.readlines()]

def height(C):
    P = []
    for i in range(W):
        p = 0
        for j in range(len(C)):
            if C[j][i] == 1:
                p = 0
            else: p += 1
        P.append(p)
    return P

def square(C):
    P = height(C)
    G = []
    L = []
    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 = L[-1][0]
            while L and v < L[-1][1]:
                a = L.pop()
                G.append((k - a[0] + 1) * a[1])
            L.append((i, 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))

Submission status: Wrong Answer

Solution code:
import sys
file = sys.stdin
H,W = map(int, file.readline().split())
C = [list(map(int,i.split())) for i in file.readlines()]

def height(C):
    P = []
    for i in range(W):
        p = 0
        for j in range(len(C)):
            if C[j][i] == 1:
                p = 0
            else: p += 1
        P.append(p)
    return P

def square(C):
    P = height(C)
    G = []
    L = []
    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((i, 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))

Submission status: Wrong Answer

Solution code:
import sys
file = sys.stdin
H,W = map(int, file.readline().split())
C = [list(map(int,i.split())) for i in file.readlines()]

def height(C):
    P = []
    for i in range(W):
        p = 0
        for j in range(len(C)):
            if C[j][i] == 1:
                p = 0
            else: p += 1
        P.append(p)
    return P

def square(C):
    P = height(C)
    G = []
    L = []
    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))
    print(ans)
    return str(max(ans))
print(ans(C))

Submission status: Wrong Answer

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

    print(max_area)

Submission status: Wrong Answer

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 - 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 last_score > score:
          last_score, last_ind = stack.pop()
          ans = max(ans, last_score * (j - last_ind))
        stack.append((score, last_ind))

print(ans)

Submission status: Time Limit Exceeded

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

h, w = map(int, readline().split())

dp = [list(map(int, readline().split())) 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] + 1

max_s = 0
for i in range(h):
    for j in range(w):
        h = dp[i][j]
        for k in range(j, w):
            if dp[i][k] == 0:
                break
            h = min(h, dp[i][k])
            s = h * ((k - j) + 1)
            if max_s < s:
                max_s = s
print(max_s)

Submission status: Time Limit Exceeded

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

    for i in range(1, max(array) + 1):
        current_area = 0
        for j in range(len(array)):
            if array[j] >= i:
                current_area += i
                if current_area > max_area:
                    max_area = current_area
            else:
                current_area = 0

    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 = max_rectangle(ans_array)
        largest_square = largest_square if largest_square > m else m

    print(largest_square)


def main():
    algorithm()


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import sys
file = sys.stdin
H,W = map(int, file.readline().split())
C = [list(map(int,i.split())) for i in file.readlines()]

def height(C):
    P = []
    for i in range(W):
        p = 0
        for j in range(len(C)):
            if C[j][i] == 1:
                p = 0
            else: p += 1
        P.append(p)
    return P

def square(C):
    P = height(C)
    G = []
    L = []
    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))

Submission status: Time Limit Exceeded

Solution code:
import sys, collections
file = sys.stdin
H,W = map(int, file.readline().split())
C = [list(map(int,i.split())) for i in file.readlines()]

def height(C):
    P = []
    for i in range(W):
        p = 0
        for j in range(len(C)):
            if C[j][i] == 1:
                p = 0
            else: p += 1
        P.append(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))

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

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

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


# from collections import namedtuple


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:]))
    # Rectangle = namedtuple('Rectangle', ('pos', 'height'))

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

"""
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)
    # print(rec_info)
    ans = solve(rec_info)
    print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

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