726 . 巴貝爾塔

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

1xlc

User's AC Ratio

100.0% (2/2)

Submission's AC Ratio

100.0% (2/2)

Tags

apcsc apcsc-greedy

Description

這裡是收錄所有的語言的巴貝爾塔（Tower of Babel）。塔內，有 $M$ 個僧人在值班，需要抄錄 $N$ 本書，編號從 $1$ 至 $N$。在已經知道第 $i$ 本書會花 $t_i$ 天抄錄完畢，而且所有的僧人都要抄錄連續編號的書的情況之下，請問這些僧人最短需要花多少時間才能夠將這些書全部抄錄完畢？請假設工作分配完畢之後，所有的僧人就會同時開始抄錄，並且會晝夜不停地抄錄，而且這些僧人只會抄錄自己被分配到的那些書。請注意，抄錄結束的時間是從所有僧人都開始抄錄開始，直到最後一個僧人抄完最後一本書為止。

Input Format

輸入有兩行。第一行有兩個正整數 $N$ 和 $M(1 \leq N, M \leq 2 \times 10^ 5)$，分別代表書本的數量和僧人的數量。第二行有 $N$ 個正整數 $t_1,t_2,t_3,\ldots,t_N(1 \leq t_i \leq 10^ 9)$ 依序代表書本需要抄錄的時間。

Output Format

請輸出一個正整數，代表這些僧人所需要的最短時間。

Sample Input 1

7 2
1 2 3 4 5 6 7

Sample Output 1

15

Sample Input 2

4 4
7 1 2 2

Sample Output 2

7

Sample Input 3

3 4
49 98 7777714

Sample Output 3

7777714

Hints

Problem Source

UVa 714

Subtasks

No. Testdata Range Constraints Score
1 0~2 範例測資 0
2 0~23 無額外限制 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 2000 524288 65536 1 2
1 2000 524288 65536 1 2
2 2000 524288 65536 1 2
3 2000 524288 65536 2
4 2000 524288 65536 2
5 2000 524288 65536 2
6 2000 524288 65536 2
7 2000 524288 65536 2
8 2000 524288 65536 2
9 2000 524288 65536 2
10 2000 524288 65536 2
11 2000 524288 65536 2
12 2000 524288 65536 2
13 2000 524288 65536 2
14 2000 524288 65536 2
15 2000 524288 65536 2
16 2000 524288 65536 2
17 2000 524288 65536 2
18 2000 524288 65536 2
19 2000 524288 65536 2
20 2000 524288 65536 2
21 2000 524288 65536 2
22 2000 524288 65536 2
23 2000 524288 65536 2
Submit
Back to Top