Các lượt nộp
    Danh sách bài
    Trang chủ
    Báo lỗi

    solution

    Đề bài: Dự trữ nước

    Ở quê Bờm có một con mương dùng để trữ nước. Dọc theo mương, người dân đặt N cột bê tông cạnh nhau, mỗi cột có cùng độ rộng và có chiều cao lần lượt là h₁, h₂, …, hₙ.

    Khi trời mưa, nước sẽ đọng lại ở những chỗ có cột thấp hơn hai bên — giống như trong các vũng trũng. Ví dụ, với dãy cột có độ cao 4 1 3 2 5 1 6, lượng nước có thể đọng lại là 10 đơn vị.

    Người dân muốn nâng bề mặt mương cho phẳng hơn, bằng cách nâng các cột thấp hơn một độ cao h nào đó lên đúng h. Tuy nhiên, họ vẫn muốn sau khi nâng, lượng nước giữ lại ít nhất là K đơn vị.

    Hãy tìm giá trị h lớn nhất sao cho khi nâng các cột thấp hơn h lên đúng h, lượng nước đọng lại không nhỏ hơn K. Nếu không tồn tại h thỏa mãn, in ra -1.

    • Định dạng đầu vào:
      • Dòng đầu gồm 2 số nguyên dương N và K (số cột và lượng nước cần giữ lại).
      • Dòng thứ hai gồm N số nguyên h₁, h₂, …, hₙ— là chiều cao từng cột.

      Giới hạn:

      • 1 ≤ N ≤ 10^5
      • 0 ≤ K ≤ 10^9
      • 1 ≤ hᵢ ≤ 10^9
    • Định dạng đầu ra:

      In ra một số nguyên duy nhất — giá trị h lớn nhất thỏa mãn điều kiện. Nếu không có giá trị nào hợp lệ, in ra -1.

    Ví dụ:

    Đầu vào:

    7 4 
4 1 3 2 5 1 6

    Đầu ra:

    3

    Đang tải editor...