Chứa Nước Giữa Hai Tường

General
Points
25
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
sortsearch
Submissions
Đề 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$
Draft saved