g421: PC.分身五河
Tags :
Accepted rate : 23人/28人 ( 82% ) [非即時]
評分方式:
Tolerant

最近更新 : 2021-11-08 08:15

Content

一年一度(?的情人節又到了。為了應付每個精靈提出的約會請求,拉塔托斯克研發出了類似刻刻帝Zaphkiel八之彈能力的裝置,讓士道可以透過召喚過去時間點中的自己,來達到分身的效果。

已知裝置可以製造出$K-1$個分身,加上本體一共有$K$個士道

共有$N$個精靈提出約會請求,而精靈們所要求的約會時間分別為 $T_1 \sim T_N$

請問共要多少時間才能讓所有精靈約會完?

*士道會按照約會請求表的順序來安排與精靈的約會*

 

對了,這是我婆↓↓ by哈哈是Kai啦

Input

給定兩個正整數 $N,K$,$1 \le N,K \le 10^6$,代表有N個人要約會,以及有K個士道。

緊接著,有 $N$ 個數字,$T_1$,...,$T_N$,代表排在第$i$ 個的人約會所需的時間。

Output

請輸出要花多少時間,才能讓所有精靈都約會完?

Sample Input #1
3 2
3 5 2
Sample Output #1
5
Sample Input #2
3 1
1 2 3
Sample Output #2
6
Sample Input #3
3 5
1 3 7
Sample Output #3
7
測資資訊:
記憶體限制: 64 MB
不公開 測資點#0 (10%): 2.0s , <1K
不公開 測資點#1 (10%): 2.0s , <1K
不公開 測資點#2 (10%): 2.0s , <10M
不公開 測資點#3 (57%): 2.0s , <1M
不公開 測資點#4 (13%): 2.0s , <10M
Hint :

範測1:

在第0分鐘時兩個士道分別約會3分鐘跟5分鐘

在第3分鐘時,其中一個士道約會結束,繼續去跟兩分鐘的約會

在第5分鐘時,所有士道結束他們的約會

輸出5為答案

 

 

10% 的測試資料滿足 $1\leq N,K \leq 3$ 而且$ 0 \leq T_i \leq 1 $

10% 的測試資料滿足 $1 \leq N \leq K \leq 10$ 而且 $0 \leq T_i \leq 10^5 $

10% 的測試資料滿足 $1 \leq N,K \leq 10^6$ 而且 $0 \leq T_i \leq 1 $

57% 的測試資料滿足 $1 \leq N,K \leq 10^6$ 而且 $0 \leq T_i \leq 10^5 $

13% 的測試資料滿足 $1 \leq N,K \leq 10^6$ 而且 $0 \leq T_i \leq 10^9 $

 

題目-Kai

狂三我婆,不服來戰

 

Tags:
出處:
[管理者:
kaihsinchen2 (Kai-Hsin Chen 2)
]


ID User Problem Subject Hit Post Date
27719
fdhs108rex (Rex Wu)
g421
題意補充(?)
154 2021-10-25 23:11