시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 8287 2019 1303 24.981%

문제

히스토그램은 직사각형 여러 개가 아래쪽으로 정렬되어 있는 도형이다. 각 직사각형은 같은 너비를 가지고 있지만, 높이는 서로 다를 수도 있다. 예를 들어, 왼쪽 그림은 높이가 2, 1, 4, 5, 1, 3, 3이고 너비가 1인 직사각형으로 이루어진 히스토그램이다.

히스토그램에서 가장 넓이가 큰 직사각형을 구하는 프로그램을 작성하시오.

입력

입력은 테스트 케이스 여러 개로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 직사각형의 수 n이 가장 처음으로 주어진다. (1 ≤ n ≤ 100,000) 그 다음 n개의 정수 h1, ..., hn (0 ≤ hi ≤ 1000000000)가 주어진다. 이 숫자들은 히스토그램에 있는 직사각형의 높이이며, 왼쪽부터 오른쪽까지 순서대로 주어진다. 모든 직사각형의 너비는 1이고, 입력의 마지막 줄에는 0이 하나 주어진다.

출력

각 테스트 케이스에 대해서, 히스토그램에서 가장 넓이가 큰 직사각형의 넓이를 출력한다.

예제 입력 1

7 2 1 4 5 1 3 3
4 1000 1000 1000 1000
0

예제 출력 1

8
4000
W3sicHJvYmxlbV9pZCI6IjY1NDkiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQ3ODhcdWMyYTRcdWQxYTBcdWFkZjhcdWI3YThcdWM1ZDBcdWMxMWMgXHVhYzAwXHVjN2E1IFx1ZDA3MCBcdWM5YzFcdWMwYWNcdWFjMDFcdWQ2MTUiLCJkZXNjcmlwdGlvbiI6IjxwPlx1ZDc4OFx1YzJhNFx1ZDFhMFx1YWRmOFx1YjdhOFx1Yzc0MCBcdWM5YzFcdWMwYWNcdWFjMDFcdWQ2MTUgXHVjNWVjXHViN2VjIFx1YWMxY1x1YWMwMCBcdWM1NDRcdWI3OThcdWNhYmRcdWM3M2NcdWI4NWMgXHVjODE1XHViODJjXHViNDE4XHVjNWI0IFx1Yzc4OFx1YjI5NCBcdWIzYzRcdWQ2MTVcdWM3NzRcdWIyZTQuIFx1YWMwMSBcdWM5YzFcdWMwYWNcdWFjMDFcdWQ2MTVcdWM3NDAgXHVhYzE5XHVjNzQwIFx1YjEwOFx1YmU0NFx1Yjk3YyBcdWFjMDBcdWM5YzBcdWFjZTAgXHVjNzg4XHVjOWMwXHViOWNjLCBcdWIxOTJcdWM3NzRcdWIyOTQgXHVjMTFjXHViODVjIFx1YjJlNFx1Yjk3YyBcdWMyMThcdWIzYzQgXHVjNzg4XHViMmU0LiBcdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LCBcdWM2N2NcdWNhYmQgXHVhZGY4XHViOWJjXHVjNzQwIFx1YjE5Mlx1Yzc3NFx1YWMwMCAyLCAxLCA0LCA1LCAxLCAzLCAzXHVjNzc0XHVhY2UwIFx1YjEwOFx1YmU0NFx1YWMwMCAxXHVjNzc4IFx1YzljMVx1YzBhY1x1YWMwMVx1ZDYxNVx1YzczY1x1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM5YzQgXHVkNzg4XHVjMmE0XHVkMWEwXHVhZGY4XHViN2E4XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2hpc3RvZ3JhbS5wbmdcIiBzdHlsZT1cImhlaWdodDoxNTlweDsgd2lkdGg6NTA2cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+XHVkNzg4XHVjMmE0XHVkMWEwXHVhZGY4XHViN2E4XHVjNWQwXHVjMTFjIFx1YWMwMFx1YzdhNSBcdWIxMTNcdWM3NzRcdWFjMDAgXHVkMDcwIFx1YzljMVx1YzBhY1x1YWMwMVx1ZDYxNVx1Yzc0NCBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Yzc4NVx1YjgyNVx1Yzc0MCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0IFx1YzVlY1x1YjdlYyBcdWFjMWNcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC4gXHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWIyOTQgXHVkNTVjIFx1YzkwNFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHVhY2UwLCBcdWM5YzFcdWMwYWNcdWFjMDFcdWQ2MTVcdWM3NTggXHVjMjE4IG5cdWM3NzQgXHVhYzAwXHVjN2E1IFx1Y2M5OFx1Yzc0Y1x1YzczY1x1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgbiAmbGU7IDEwMCwwMDApIFx1YWRmOCBcdWIyZTRcdWM3NGMgblx1YWMxY1x1Yzc1OCBcdWM4MTVcdWMyMTggaDxzdWI+MTxcL3N1Yj4sIC4uLiwgaDxzdWI+bjxcL3N1Yj4gKDAgJmxlOyBoPHN1Yj5pPFwvc3ViPiAmbGU7IDEwMDAwMDAwMDApXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjNzc0IFx1YzIyYlx1Yzc5MFx1YjRlNFx1Yzc0MCBcdWQ3ODhcdWMyYTRcdWQxYTBcdWFkZjhcdWI3YThcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YzljMVx1YzBhY1x1YWMwMVx1ZDYxNVx1Yzc1OCBcdWIxOTJcdWM3NzRcdWM3NzRcdWJhNzAsIFx1YzY3Y1x1Y2FiZFx1YmQ4MFx1ZDEzMCBcdWM2MjRcdWI5NzhcdWNhYmRcdWFlNGNcdWM5YzAgXHVjMjFjXHVjMTFjXHViMzAwXHViODVjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViYWE4XHViNGUwIFx1YzljMVx1YzBhY1x1YWMwMVx1ZDYxNVx1Yzc1OCBcdWIxMDhcdWJlNDRcdWIyOTQgMVx1Yzc3NFx1YWNlMCwgXHVjNzg1XHViODI1XHVjNzU4IFx1YjljOFx1YzljMFx1YjljOSBcdWM5MDRcdWM1ZDBcdWIyOTQgMFx1Yzc3NCBcdWQ1NThcdWIwOTggXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYywgXHVkNzg4XHVjMmE0XHVkMWEwXHVhZGY4XHViN2E4XHVjNWQwXHVjMTFjIFx1YWMwMFx1YzdhNSBcdWIxMTNcdWM3NzRcdWFjMDAgXHVkMDcwIFx1YzljMVx1YzBhY1x1YWMwMVx1ZDYxNVx1Yzc1OCBcdWIxMTNcdWM3NzRcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjY1NDkiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJMYXJnZXN0IFJlY3RhbmdsZSBpbiBhIEhpc3RvZ3JhbSIsImRlc2NyaXB0aW9uIjoiPHA+QSBoaXN0b2dyYW0gaXMgYSBwb2x5Z29uIGNvbXBvc2VkIG9mIGEgc2VxdWVuY2Ugb2YgcmVjdGFuZ2xlcyBhbGlnbmVkIGF0IGEgY29tbW9uIGJhc2UgbGluZS4gVGhlIHJlY3RhbmdsZXMgaGF2ZSBlcXVhbCB3aWR0aHMgYnV0IG1heSBoYXZlIGRpZmZlcmVudCBoZWlnaHRzLiBGb3IgZXhhbXBsZSwgdGhlIGZpZ3VyZSBvbiB0aGUgbGVmdCBzaG93cyB0aGUgaGlzdG9ncmFtIHRoYXQgY29uc2lzdHMgb2YgcmVjdGFuZ2xlcyB3aXRoIHRoZSBoZWlnaHRzIDIsIDEsIDQsIDUsIDEsIDMsIDMsIG1lYXN1cmVkIGluIHVuaXRzIHdoZXJlIDEgaXMgdGhlIHdpZHRoIG9mIHRoZSByZWN0YW5nbGVzOjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2hpc3RvZ3JhbS5wbmdcIiBzdHlsZT1cImhlaWdodDoxNTlweDsgd2lkdGg6NTA2cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+VXN1YWxseSwgaGlzdG9ncmFtcyBhcmUgdXNlZCB0byByZXByZXNlbnQgZGlzY3JldGUgZGlzdHJpYnV0aW9ucywgZS5nLiwgdGhlIGZyZXF1ZW5jaWVzIG9mIGNoYXJhY3RlcnMgaW4gdGV4dHMuIE5vdGUgdGhhdCB0aGUgb3JkZXIgb2YgdGhlIHJlY3RhbmdsZXMsIGkuZS4sIHRoZWlyIGhlaWdodHMsIGlzIGltcG9ydGFudC4gQ2FsY3VsYXRlIHRoZSBhcmVhIG9mIHRoZSBsYXJnZXN0IHJlY3RhbmdsZSBpbiBhIGhpc3RvZ3JhbSB0aGF0IGlzIGFsaWduZWQgYXQgdGhlIGNvbW1vbiBiYXNlIGxpbmUsIHRvby4gVGhlIGZpZ3VyZSBvbiB0aGUgcmlnaHQgc2hvd3MgdGhlIGxhcmdlc3QgYWxpZ25lZCByZWN0YW5nbGUgZm9yIHRoZSBkZXBpY3RlZCBoaXN0b2dyYW0uPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgaW5wdXQgY29udGFpbnMgc2V2ZXJhbCB0ZXN0IGNhc2VzLiBFYWNoIHRlc3QgY2FzZSBkZXNjcmliZXMgYSBoaXN0b2dyYW0gYW5kIHN0YXJ0cyB3aXRoIGFuIGludGVnZXIgbiwgZGVub3RpbmcgdGhlIG51bWJlciBvZiByZWN0YW5nbGVzIGl0IGlzIGNvbXBvc2VkIG9mLiBZb3UgbWF5IGFzc3VtZSB0aGF0IDEmbHQ7PW4mbHQ7PTEwMDAwMC4gVGhlbiBmb2xsb3cgbiBpbnRlZ2VycyBoPHN1Yj4xPFwvc3ViPiwuLi4saDxzdWI+bjxcL3N1Yj4sIHdoZXJlIDAmbHQ7PWg8c3ViPmk8XC9zdWI+Jmx0Oz0xMDAwMDAwMDAwLiBUaGVzZSBudW1iZXJzIGRlbm90ZSB0aGUgaGVpZ2h0cyBvZiB0aGUgcmVjdGFuZ2xlcyBvZiB0aGUgaGlzdG9ncmFtIGluIGxlZnQtdG8tcmlnaHQgb3JkZXIuIFRoZSB3aWR0aCBvZiBlYWNoIHJlY3RhbmdsZSBpcyAxLiBBIHplcm8gZm9sbG93cyB0aGUgaW5wdXQgZm9yIHRoZSBsYXN0IHRlc3QgY2FzZS48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCB0ZXN0IGNhc2Ugb3V0cHV0IG9uIGEgc2luZ2xlIGxpbmUgdGhlIGFyZWEgb2YgdGhlIGxhcmdlc3QgcmVjdGFuZ2xlIGluIHRoZSBzcGVjaWZpZWQgaGlzdG9ncmFtLiBSZW1lbWJlciB0aGF0IHRoaXMgcmVjdGFuZ2xlIG11c3QgYmUgYWxpZ25lZCBhdCB0aGUgY29tbW9uIGJhc2UgbGluZS48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

Contest > University of Ulm Local Contest > University of Ulm Local Contest 2003 H번

  • 문제를 번역한 사람: baekjoon
  • 어색한 표현을 찾은 사람: eric00513
  • 데이터를 추가한 사람: kth004