시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
3 초 (추가 시간 없음) | 1024 MB | 81 | 41 | 34 | 49.275% |
레프는 너비가 1이고, 높이가 h1, ⋯, hN인 N개의 막대기들이 많이 있다. 레프는 이 막대기들을 사용해서 학생들에게 히스토그램에 완전히 포함되는 직사각형 중 넓이가 가장 큰 것을 구하는 문제를 내려고 한다.
N명의 학생들에게는 서로 다른 문제를 내야 하는데, 히스토그램을 만들 막대기 종류가 부족했던 레프는 다음과 같이 너비가 (N − 1)인 히스토그램을 N개 만들기로 했다.
Hi에서의 직사각형 넓이의 최댓값을 Si라고 하자. S1, ⋯, SN을 구하는 프로그램을 작성하여, 레프가 편하게 채점할 수 있도록 도와주자!
첫째 줄에 양의 정수 N이 주어진다. (2 ≤ N ≤ 500 000)
둘째 줄에 N개의 정수 h1, ⋯, hN이 공백으로 구분되어 주어진다. (1 ≤ hi ≤ 109)
첫째 줄에 N개의 정수 S1, ⋯, SN을 공백으로 구분하여 출력한다.
6 1 4 3 6 2 5
10 8 8 8 12 9
University > 서울대학교 > 2022 서울대학교 프로그래밍 경시대회 > Division 1 I번
University > 서울대학교 > 2022 서울대학교 프로그래밍 경시대회 > Division 1 (Open Contest) I번