Trên một dòng sông người ta xây dựng các đập thủy điện có chiều cao khác nhau. Sau đó người ta muốn tính số lượng nước tối đa ma các đập thủy điện này có thể chứa được.
Đầu vào:
số lượng test case T (1 =< T <= 20 ) tiếp theo là 2 dòng, dòng 1 chứa số lượng đập thủy điện, dòng thứ 2 là chiều cao của từng đập.
Đầu ra:
In số lượng nước tối đa mà các đập giữ lại được.
Đầu vào:
số lượng test case T (1 =< T <= 20 ) tiếp theo là 2 dòng, dòng 1 chứa số lượng đập thủy điện, dòng thứ 2 là chiều cao của từng đập.
Đầu ra:
In số lượng nước tối đa mà các đập giữ lại được.
Ví dụ
Hướng dẫn giải:
Tại 1 vị trí cột i tìm cột cao nhất bên trái và cột cao nhất bên phải, lượng nước lưu trữ tại cột sẽ là min(left_high, right_high) - high[i]. Chú ý cũng có trường hợp 1 trong 2 bên không có cột nào cao hơn chiều cao của cột i.
Tại 1 vị trí cột i tìm cột cao nhất bên trái và cột cao nhất bên phải, lượng nước lưu trữ tại cột sẽ là min(left_high, right_high) - high[i]. Chú ý cũng có trường hợp 1 trong 2 bên không có cột nào cao hơn chiều cao của cột i.