TopCoder

Thumb emilia
rsabcmoi
Yes? No? Yes! Yes!

User's AC Ratio

53.3% (8/15)

Submission's AC Ratio

15.5% (18/116)

Description

你聽過樓下的房客嗎?

據說,在一個遙遠的國度,有個名叫希爾伯特的人,收了無限多個房客。雖然希爾伯特的房間已經住滿了,然而這些房客住的房間編號是從0開始的全體非負整數,所以不管來了多少(有限個)房客,希爾伯特總是能收容他們,不過這又是另一個故事了。

話說有一次,希爾伯特煮了幾個鬆餅給前$n$個房客吃,其中住在編號是$i$的房客拿到了$P_i$個鬆餅。然而這個鬆餅很容易就冷掉了,所以這些房客決定和其它房客共享鬆餅。在每一分鐘,每個房客可以吃掉一個鬆餅,或者分一些些鬆餅給另一個房客(不一定要是前$n$個房客)。然而希爾伯特並不喜歡自己的好意一直不斷地被這樣分發掉(看起來他很傲嬌),所以他規定房客們分鬆餅的總次數不能超過一個數$B$。儘管如此,這些房客還是想要在最快的時間內將鬆餅吃完。然而,無窮多個人聚在一起討論是一件非常麻煩的事,所以這些人拜託你,希爾伯特的學生,解決他們的煩惱。

如果你失敗的話,你會被無限多個人圍毆至死。
如果你成功的話,你會解出希爾伯特的第三個問題。

Input Format

第一行有兩個整數$1\leq n\leq 10^ 5, 0\leq B\leq 10^ 6$,代表前$n$個房客拿到了鬆餅而且他們總共只能分鬆餅$B$次。
緊接著的一行有$n$個正整數$P_0, P_1,\dots, P_{n-1}$,其中$P_i\leq 10^ 6$代表第$i$個人拿到的鬆餅數。

子任務(測資) 額外限制 分數
1 (0~4) $B\leq 25$ 13
2 (5~9) $B\leq 75$ 12
3 (10~14) 無限制 75

Output Format

請輸出一行代表所有鬆餅最快能在幾分鐘內吃完。

Sample Input

3 2
3 4 9

Sample Output

5

Hints

一種在五分鐘內吃完的方法:
第一分鐘時編號0, 1的房客吃一個鬆餅,編號2的房客分給編號3的房客三個鬆餅。
第二分鐘時編號0,1,3的房客吃一個鬆餅,編號2的房客分給編號4的房客三個鬆餅。
接下來的時間大家都自己吃自己的鬆餅。

Problem Source

Problem set / Description by Paupière
建國中學105學年度校內第一次模擬賽pE
題目取自2015 TOI第二階段選訓第三次模擬考pC

Subtasks

For Testdata: 0 ~ 4, Score: 13
For Testdata: 5 ~ 9, Score: 12
For Testdata: 10 ~ 14, Score: 75
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 1000 65536 65536
1 1000 65536 65536
2 1000 65536 65536
3 1000 65536 65536
4 1000 65536 65536
5 1000 65536 65536
6 1000 65536 65536
7 1000 65536 65536
8 1000 65536 65536
9 1000 65536 65536
10 1000 65536 65536
11 1000 65536 65536
12 1000 65536 65536
13 1000 65536 65536
14 1000 65536 65536