시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 256 MB | 1960 | 763 | 679 | 51.245% |
상렬이에게는 히스토그램 모양의 플라스틱 퍼즐 조각이 많이 있다. 상렬이는 이 퍼즐 조각들이 필요가 없어져 버릴 계획이다. 하지만 갑자기 플라스틱 판이 많이 필요해져 퍼즐에서 직사각형 모양을 잘라내 재활용하려고 한다.
퍼즐의 모양이 주어질 때 자를 수 있는 가장 큰 직사각형의 넓이를 구하는 프로그램을 작성하라.
히스토그램의 정보는 히스토그램을 구성하는 직사각형들의 높이로 주어진다. 각 직사각형의 너비는 1로 모두 같다.
히스토그램을 구성하는 직사각형의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 이어 N개의 줄에 걸쳐 각 직사각형의 높이인 정수 Hi(1 ≤ Hi ≤ 1,000,000)가 주어진다.
잘라낼 수 있는 직사각형의 최대 넓이를 출력하라.
3 7 3 4
9