Lượng nước mưa đọng lại
Points
26
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
array1d
Đề bài
Cho một mảng $H$ gồm $n$ số nguyên không âm biểu diễn độ cao của các cột liền kề có chiều rộng bằng $1$. Sau khi trời mưa, hãy tính tổng lượng nước tối đa có thể đọng lại giữa các cột.
Dữ liệu vào
Dòng đầu chứa số nguyên $n$. Dòng thứ hai chứa $n$ số nguyên không âm $H_1, H_2, \dots, H_n$.
Dữ liệu ra
Một số nguyên duy nhất là tổng lượng nước đọng lại.
Ví dụ
Input
12
0 1 0 2 1 0 1 3 2 1 2 1
Output
6
Giới hạn
$1 \le n \le 2 \cdot 10^5$, $0 \le H_i \le 10^9$.
Community Discussion