Chăm sóc hàng cây

Binary-search Buổi 13 — Chặt nhị phân đáp án greedy
Points
22
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
sortsearch
Submissions
Đề bài

Trong vườn có $N$ chậu cây xếp thành hàng ngang, chậu thứ $i$ hiện có chiều cao $a_i$. Trong $M$ ngày liên tiếp, mỗi ngày bạn được chọn một đoạn gồm đúng $W$ chậu cây liên tiếp và tưới thuốc kích thích làm chiều cao của cả $W$ chậu cây đó tăng thêm $1$.

Hãy tìm chiều cao nhỏ nhất lớn nhất có thể của chậu cây thấp nhất sau $M$ ngày.

Dữ liệu vào
  • Dòng đầu tiên chứa ba số nguyên $N, M, W$.
  • Dòng thứ hai chứa $N$ số nguyên $a_1, a_2, \dots, a_N$.
Dữ liệu ra

In ra chiều cao nhỏ nhất lớn nhất có thể đạt được.

Ví dụ
Input Output
6 2 3

2 2 2 2 1 1 | 2 | | 2 5 1 5 8 | 9 |

Giới hạn
  • $1 \le W \le N \le 10^5$
  • $1 \le M \le 10^5$
  • $1 \le a_i \le 10^9$.
Draft saved