USACO 2018 - Dec - Silver - Convention

View as PDF

Submit solution

Points: 0.20 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout

Suggester:
Problem source:
http://www.usaco.org/index.php?page=viewproblem2&cpid=858
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Nông dân John chuẩn bị tổ chức một hội nghị về ăn cỏ tại trang trại của anh ấy

Bò từ khắp tới trên thế giới đang bay tới sân bay gần đó thể tham dự hội nghị và ăn cỏ. Chính xác hơn, Có ~N~ con bò đang đến ~(1 \leq N \leq 10^5)~ and con bò thứ i đến sân bay tại thời điểm ~t_i (0 \leq t_i \leq 10^9)~. Nông dân John đã sắp xếp ~M ( 1 \leq M \leq 10^5)~ xe buýt để chở những con bò về từ sân bay. Mỗi xe có thể chứa ~C~ con bò trong nó ~(1 \leq C \leq N)~. Nông dân John muốn sắp xếp những con bò vào các xe buýt. Một xe buýt có thể rời đi chỉ khi con bò đến sân bay sau cùng được xếp vào xe buýt đó lên xe buýt. Nông dân John không muốn những con bò phải đợi lâu. Thế nên, anh ấy muốn biết thời gian chờ tối đa bé nhất của một con bò bất kì nếu anh ấy sắp xếp xe buýt hợp lí. Thời gian chờ của một con bò là khoảng cách giữa thời điểm nó đến sân bay và thời điểm xe buýt nó được xếp vào rời đi.

Đảm bảo ~M*C \geq N~

Input

Dòng đầu tiên là ba số nguyên dương ~N, M, C~. ~N~ dòng tiếp, mỗi dòng chứa một số nguyên ~t_i~ là thời điểm con bò thứ i đến sân bay.

Output

In ra thời gian chờ tối đa bé nhất có thể nếu sắp xếp xe buýt hợp lí.

Sample Input

6 3 2
1 1 10 14 4 3

Sample Output

4

Giải thích

Nếu hai con bò đến vào thời điểm 1 vào chung xe buýt thứ nhất, hai con bò đến vào thời điểm 3 và 4 cùng vào chung xe buýt thứ hai, và hai con bò đến vào thời điểm 10 và 14 vào xe buýt thứ ba, thì thời gian chờ lâu nhất một con bò là 4 đơn vị thời gian (bò đến vào thời điểm 10 chờ từ thời điểm 10 đến thời điểm 14).


Comments

Please read the guidelines before commenting.


There are no comments at the moment.