TopCoder

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

User's AC Ratio

94.7% (54/57)

Submission's AC Ratio

69.9% (86/123)

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

No. Testdata Range Score
1 0~1 7
2 0~3 16
3 4~6 9
4 4~9 7
5 4~13 8
6 0~17 53

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 900 65536 262144 1 2 6
1 900 65536 262144 1 2 6
2 900 65536 262144 2 6
3 900 65536 262144 2 6
4 900 65536 262144 3 4 5 6
5 900 65536 262144 3 4 5 6
6 900 65536 262144 3 4 5 6
7 900 65536 262144 4 5 6
8 900 65536 262144 4 5 6
9 900 65536 262144 4 5 6
10 900 65536 262144 5 6
11 900 65536 262144 5 6
12 900 65536 262144 5 6
13 900 65536 262144 5 6
14 500 65536 262144 6
15 500 65536 262144 6
16 500 65536 262144 6
17 500 65536 262144 6