Vừa đủ nước
Đề bài
Mô tả
Có thể bạn còn nhớ, trong bài Reservoir của kỳ thi ICPC Nha Trang Regional 2016, chúng ta đã xây một hồ chứa nước gần sông Hồng. Hồ chứa có thể xem như một hình hộp chữ nhật có chiều rộng đơn vị. Chiều dài của nó được chia thành đoạn dài đơn vị, đoạn thứ có chiều cao đơn vị. Ta coi hai đầu trái và phải của hồ có chiều cao , tức là .
Sau cơn mưa, một số đoạn của hồ chứa đầy nước. Tất nhiên nước chảy từ chỗ cao xuống chỗ thấp, nên nước có thể chảy ra ngoài ở cả hai đầu trái và phải của hồ.
Hình dưới đây là mặt cắt của hồ theo chiều dài và chiều cao với , (# là thành hồ, ~ là nước; hàng trên cùng ứng với độ cao ). Hồ chứa được đơn vị nước.
. # ~ ~ ~ # . . .
. # ~ ~ ~ # . . .
. # ~ # # # ~ # .
# # # # # # # # #
Người ta thấy rằng hồ chưa chứa đủ nước, nên quyết định nâng chiều cao của một số đoạn. Nâng một đoạn lên đơn vị tốn đô la. Tổng ngân sách là đô la.
Hỏi hồ có thể chứa tối đa bao nhiêu đơn vị nước?
Dữ liệu vào
- Dòng đầu tiên chứa hai số nguyên và ().
- Dòng thứ hai chứa đúng số nguyên (), chiều cao của đoạn.
Dữ liệu ra
In ra một số nguyên là lượng nước tối đa mà hồ có thể chứa.
Ràng buộc
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 9 2 1 4 1 2 2 4 1 2 1 |
11 | Nâng đoạn và đoạn thêm đơn vị (lên độ cao ), mỗi đoạn chứa thêm đơn vị nước, tổng cộng . |
| 3 1 2 1 2 |
1 | Ví dụ thêm. Nâng một trong hai thành không giúp gì vì nước tràn qua thành còn lại; hồ giữ đơn vị nước như ban đầu. |
Bình luận