Chứa Nước Giữa Hai Tường
Points
25
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
sortsearch
Đề bài
Có $N$ bức tường thẳng đứng đặt song song cách đều nhau, đánh số từ $1$ đến $N$. Bức tường thứ $i$ đặt tại tọa độ $i$ và có chiều cao $h_i$.
Hãy chọn hai bức tường $i < j$ sao cho cùng với mặt đất, chúng tạo thành một bể chứa được nhiều nước nhất. Lượng nước chứa được bằng $(j - i) \times \min(h_i, h_j)$.
Dữ liệu vào
- Dòng đầu tiên chứa số nguyên $N$ ($2 \le N \le 2 \cdot 10^5$).
- Dòng thứ hai chứa $N$ số nguyên $h_1, h_2, \dots, h_N$ ($0 \le h_i \le 10^9$).
Dữ liệu ra
- Một số nguyên duy nhất là lượng nước lớn nhất chứa được.
Ví dụ
| Input | Output |
|---|---|
| 9 1 8 6 2 5 4 8 3 7 |
49 |
Giới hạn
- $2 \le N \le 2 \cdot 10^5$
- $0 \le h_i \le 10^9$
Community Discussion