Lượng nước tối đa
Mỗi hàng cọc bê tông được đóng sát kín nhau, khi đổ nước vào thì các cọc thấp sẽ chứa nước nếu có những cọc cao ngăn cho.
Ví dụ nếu các cọc bê tông được đóng xếp theo thứ tự \(3, 7, 2, 1, 5, 2, 4\):
Cho độ dài của \(n\) cọc bê tông, giả sử bề ngang của mỗi cọc là một đơn vị, hãy tính lượng nước tối đa mà các cọc bê tông có thể chứa khi được đóng liền thành một hàng, với thứ tự tùy ý.
Đầu vào
Dòng đầu tiên chứa số tự nhiên \(n\) \((3 \le n \le 2*10^5)\), số lượng cọc.
Dòng tiếp theo gồm \(n\) số nguyên dương không quá \(10^9\), chiều cao của mỗi cọc.
Đầu ra
Một số tự nhiên duy nhất là kết quả bài toán.
Subtask
\(30\%\) số test có \(n \le 1000\).
Ví dụ
Đầu vào 1:
5
1 2 4 4 8Đầu ra 1:
5Giải thích: Xếp các cọc lần lượt theo thứ tự \(4, 1, 2, 4, 8\) cho ta lượng nước lớn nhất là \(5\) (nước đọng trên cột \(1\) là \(3\) khối, đọng trên cột \(2\) là \(2\) khối).
Đầu vào 2:
5
5 5 5 5 5Đầu ra 2:
0
Comments
bai nay hay v