Nội dung Bài tập
- Mã:
- BECHUA
- Tên:
- Bể chứa nước
- Dạng thi:
- oi
- Thang điểm:
- 10 điểm
- Giới hạn thời gian:
- 1 giây
- Giới hạn bộ nhớ:
- 256 MB
- Được tạo bởi:
- 4901103064
Vào những dịp hè, thời tiết thường có xu hướng oi bức, và nhà nhà ai cũng đều cần phải tích trữ nước để dành sử dụng. Nhà bạn Phú có một cái giếng nước được cấu tạo từ n cột đá, mỗi cột đá đều có chiều cao ban đầu. Khi đổ nước vào giếng, nước ở trong giếng sẽ được giữ lại nếu ở bên trái và bên phải của giếng có một cột đá khác có thể chặn được lượng nước đó, ngược lại nước sẽ bị tràn đi mất.
Bạn Phú thì cũng không phải là người khá giả, chỉ có một số vốn k đô-la để đầu tư việc xây thêm đá cho các cột. Cứ một viên đá thì tương ứng với một đô-la. Mục tiêu của bạn Phú là bằng cách thần kì nào đó, chỉ bỏ ra chừng đó số tiền mà xây được giếng nước có thể chứa được nhiều nước nhất.
Yêu cầu:
-
Tính lượng nước đọng lại ban đầu (khi chưa tăng).
-
Tìm lượng nước đọng lớn nhất có thể sau khi thực hiện đúng k lần tăng chiều cao.
Input:
-
Dòng đầu tiên chứa 2 số nguyên n và k (1 ≤ n, k ≤ 12).
-
Dòng thứ hai chứa n số nguyên hi (1 ≤ hi ≤ 10^9, 0 ≤ i ≤ n-1): chiều cao ban đầu của các cột.
Output:
-
Dòng đầu tiên in: Luong nuoc ban dau: X
-
Dòng thứ hai in: Luong nuoc luc sau: Y
Trong đó: X là lượng nước ban đầu có thể trữ, Y là lượng nước lớn nhất có thể trữ sau khi tăng chiều cao đúng k lần.
Ví dụ:
Input
Output
5 3
1 2 1 2 1
Luong nuoc ban dau: 1
Luong nuoc luc sau: 3
Ví dụ:
Input
Output
9 2
1 4 1 2 2 4 1 2 1
Luong nuoc ban dau: 8
Luong nuoc luc sau: 11
Giải thích chi tiết:
Theme :
Mời bạn soạn code
Ai có thể xem bài này :
Thông tin
Phần thảo luận