trang chủ / đề bài / icpc20_nat_j

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 1 đơn vị. Chiều dài của nó được chia thành n đoạn dài 1 đơn vị, đoạn thứ i có chiều cao hi đơn vị. Ta coi hai đầu trái và phải của hồ có chiều cao 0, tức là h0=hn+1=0.

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 n=9, h=[1,4,1,2,2,4,1,2,1] (# là thành hồ, ~ là nước; hàng trên cùng ứng với độ cao 4). Hồ chứa được 8 đơ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 1 đơn vị tốn 1 đô la. Tổng ngân sách là k đô 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 n và k (1≤n,k≤12).
  • Dòng thứ hai chứa đúng n số nguyên h1,h2,…,hn (1≤hi≤109), chiều cao của n đ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

  • 1≤n,k≤12
  • 1≤hi≤109

Ví dụ

Input Output Giải thích
9 2
1 4 1 2 2 4 1 2 1
11 Nâng đoạn 2 và đoạn 6 thêm 1 đơn vị (lên độ cao 5), mỗi đoạn 3,4,5 chứa thêm 1 đơn vị nước, tổng cộng 8+3=11.
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ữ 1 đơn vị nước như ban đầu.

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0