만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

직사각형 마른 땅

면접 대비

시간 제한7초메모리 제한1024 MB

요약
0과 1로 이루어진 격자에서 1(습지)이 없는 가장 큰 직사각형의 넓이를 구합니다.
난이도

보통10점 중 5점

유형
행렬, 스택, 동적 계획법
정답자
아직 제출이 없습니다

문제

플로리다에는 습지가 많아서 집을 지을 땅을 찾기 어렵다. 사람들이 집을 반드시 직사각형으로 짓겠다고 고집하면 이 문제는 더 심각해진다.

땅은 2차원 직사각형 격자이고, 각 칸은 젖은 땅이거나 마른 땅이다. 넓이가 가장 큰 직사각형 마른 땅을 찾아라. 즉 넓이가 가장 큰 집을 지을 수 있는 곳을 찾는 것이다. 집은 직사각형이어야 하므로, 사용하는 마른 칸들은 직사각형을 이루어야 하며 그 직사각형 안에 젖은 칸이 하나도 없어야 한다.

입력

첫 줄에 두 정수 rr (1≤r≤2001 \le r \le 200)과 cc (1≤c≤2001 \le c \le 200)가 주어진다. 각각 땅의 행 수와 열 수이다.

이어지는 rr개의 줄은 땅의 각 행을 나타낸다. 각 줄은 1번 열부터 시작하는 cc개의 문자로 이루어지며, 각 문자는 1(젖은 땅) 또는 0(마른 땅)이다.

출력

가장 넓은 직사각형 마른 땅의 넓이를 출력한다.

예제3

  1. 예제 1

    입력
    4 5
    10010
    01111
    11110
    00001
    
    예상 출력
    6
    
  2. 예제 2

    입력
    3 2
    10
    11
    11
    
    예상 출력
    4
    
  3. 예제 3

    입력
    2 2
    10
    01
    
    예상 출력
    1