g424: PF.抱ㄌㄌ
Tags :
Accepted rate : 5人/11人 ( 45% ) [非即時]
評分方式:
Tolerant

最近更新 : 2021-10-15 17:22

Content

熊頭喜歡ㄌㄌ,所以他想抱ㄌㄌ回家

最近$n$天都會有ㄌㄌ出沒,抱回家就能獲得$a_i$的幸福值

每天熊頭都可以選擇要不要抱ㄌㄌ回家

可是因為有萬惡的IBF存在,熊頭最多只能連續抱走$k$個ㄌㄌ

如果連續$k+1$天都抱ㄌㄌ回家,會被IBF抓走

熊頭不知道要怎麼抱才好,請你寫個程式幫熊頭判斷在不被IBF抓走的情況下,最多能獲得多少幸福值

 

 

Input

第一行有兩個整數$n,k$表有n個ㄌㄌ,最多連續取k個ㄌㄌ

第二行有$n$個整數$a_i$表抱走第i個ㄌㄌ的幸福值

 

保證所有測資符合

$1 \le n,k \le 10^5$

$0 \le a_i \le 10^9$

Output

輸出不被IBF抓走的最大幸福值

Sample Input #1
6 2
3 5 1 6 2 4
Sample Output #1
18
Sample Input #2
10 3
23 54 12 20 48 32 59 74 15 23
Sample Output #2
301
測資資訊:
記憶體限制: 64 MB
不公開 測資點#0 (33%): 2.0s , <1M
不公開 測資點#1 (33%): 2.0s , <1M
不公開 測資點#2 (34%): 2.0s , <1M
Hint :

範測1說明:

抱第(0,1,3,5)個ㄌㄌ回家 

能獲得最大幸福值(3+5+6+4)=18

 

subtask1 (33%) : $1 \le n \le 10^3 , k=1$

subtask2 (44%) : $1 \le n,k \le 10^3$

subtask3 (23%) : $1 \le n,k \le 10^5$

 

題目-ub33

p.s感謝Kai的隔壁的隔壁的*n的電神ㄌㄌ控室友提供的題目

本題所出現專有名詞、組織機構皆為虛構,如有雷同應屬巧合

然後ㄌㄌ真的很棒 推薦大家來抱

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


ID User Problem Subject Hit Post Date
27806
r1cky (木叢欉木叢)
g424
Java 解題心得
135 2021-10-30 19:05