TopCoder

Thumb hsnu2016
Adrien Wu
$ \begin{align} AC \times 2^9 \\ \text{New TIOJ ?} \end{align} $

User's AC Ratio

92.5% (49/53)

Submission's AC Ratio

71.1% (81/114)

Description

去買飲料的時候,最怕遇到前面的客人一次購買很多杯飲料,如此一來,即使排隊人數很少,一樣要等很久。

有一天,你經過了一家飲料店,發現有$N$個人排隊要買飲料。不過,這家飲料店人手充足,一共有$M$個店員可以服務這些排隊的人潮。
為了公平起見,雖然店員很多,但是排隊只排成一列,避免在排很多列的情況下,每列前進的速度會不一樣。

另外,為了服務品質起見,這家店的店員必須遵守兩個規則:必須按照客人排隊順序服務客人,不能先服務排在後面的顧客,否則前面的客人可能會森77(而這是飲料店最不想看到的狀況);另外,如果某個店員服務了某個客人,則該客人點的所有飲料都要由該店員製作,製作完成之後才能服務下一位客人。

你做了一下市場調查,詢問每位排隊的客人要買幾杯飲料。假如所有的店員製作飲料的速度都是每分鐘1杯,在遵守這些規則的前提下,請問服務完這些客人至少需要多久?

Input Format

輸入第一行有兩個正整數$N,M$,分別代表排隊等待的客人數量,以及店員數量。
接下來會有$N$個以空白隔開的正整數,依序為每位排隊顧客要購買的飲料數量。

對於所有測資,$N\leq 10^ 6, M\leq 10^ 4$,每個客人要購買的飲料數不超過1000。

子任務(測資)額外限制分數
1(0~1)$M=1$7
2(0~3)$M\leq 2$16
3(4~6)$N, M \leq 20$9
4(4~9)$N \leq 10^ 4$7
5(4~13)$N \leq 10^ 5$8
6(0~17)無限制53

Output Format

輸出一行包含一個整數,代表服務完這些客人至少需要幾分鐘。

Sample Input

5 2
1 5 2 1 1

Sample Output

5

Hints

假設初始時間為0,五個客人的飲料分別在時間點0, 0, 1, 3, 4開始製作(其中一位店員負責第二位客人,另外一位負責其他四位);製作完成的時間分別是1, 5, 3, 4, 5。

Problem Source

建國中學106學年度校隊選拔:複試pA

Subtasks

For Testdata: 0 ~ 1, Score: 7
For Testdata: 0 ~ 3, Score: 16
For Testdata: 4 ~ 6, Score: 9
For Testdata: 4 ~ 9, Score: 7
For Testdata: 4 ~ 13, Score: 8
For Testdata: 0 ~ 17, Score: 53
No. Time Limit (ms) Memory Limit (KiB)
0 900 65536
1 900 65536
2 900 65536
3 900 65536
4 900 65536
5 900 65536
6 900 65536
7 900 65536
8 900 65536
9 900 65536
10 900 65536
11 900 65536
12 900 65536
13 900 65536
14 500 65536
15 500 65536
16 500 65536
17 500 65536