output_description: Print the area (the number of 0s) of the largest rectangle.
input_description: 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 × W matrix, are
  given.
attempt: 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)
  
problem_description: Largest Rectangle
  
  Given a matrix (H × W) which contains only 1 and 0, find the area of the
  largest rectangle which only contains 0s.
samples: [{"input": "5\n    0 0 1 0 0\n    1 0 0 0 0\n    0 0 0 1 0\n    0 0 0 1 0", "output": "6"}]