R03497
Trapping Rain Water
실버 II레이팅
의견: 0
설명
나란히 서 있는 \(N\)개의 음이 아닌 막대 높이가 주어질 때, 비가 온 뒤 막대 사이에 갇히는 물의 총량을 구한다. 위치 \(i\) 위의 물 높이는 \(\min(\max_{j\le i} h_j, \max_{j\ge i} h_j)\)이며, 그곳에 갇히는 양은 그 값에서 \(h_i\)를 뺀 값이다(음수는 \(0\)).
제약
입력 형식
첫 줄에 \(N\) (\(1 \le N \le 10^5\))이 주어진다. 둘째 줄에 각각 \([0, 10^4]\)인 정수 \(N\)개가 주어진다.
출력 형식
갇힌 물의 총량을 출력한다.
예제 1
입력
12
0 1 0 2 1 0 1 3 2 1 2 1
출력
6
예제 2
입력
6
4 2 0 3 2 5
출력
9
예제 3
입력
3
1 2 3
출력
0
문제 정보
riseoj 작성
출처 RiseOJ Basics
태그
평가 및 의견
Trapping Rain Water
개별 의견
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Trapping Rain Water
게스트로 둘러보고 있습니다. 로그인하면 풀이를 제출하고 진행 상황을 확인할 수 있습니다.
로그인하고 제출하기