f174: m6a2-蛋糕(Cake)
Tags : 前綴和 單調隊列
Accepted rate : 9人/21人 ( 43% ) [非即時]
評分方式:
Tolerant

最近更新 : 2020-08-29 12:20

Content

TOI練習賽 2020m6a2-蛋糕(Cake)    原題連結

小明過生日,家人為他準備一個長方型的水果蛋糕,由於他是壽星,他可以先切蛋糕去吃。這個蛋糕分成 N 小塊,每塊都有一種餡料。
小明對每種餡料有不同的喜好度,喜好度數值若為正值代表喜歡,負值代表厭惡,零值為沒有感覺。 為了省時間,小明只挑連續一段蛋糕來吃,
這樣就只要切一刀或兩刀。而且,為了讓其它人也能吃到蛋糕,他「至多」只會挑 K小塊的份量吃,(可以不拿滿 K小塊分量的蛋糕,甚至是不拿)。
舉例而言:假如 N=7、K=3,每小塊蛋糕小明 給的喜好度評分如下: 3 7 -1 9 2 2 1
拿到[7, -1, 9]這三塊蛋糕的總分最高,為 15分,縱使中間的他不喜歡吃 也沒關係。雖然[9, 2, 2]這段蛋糕他全部都喜歡,不過總分只有 13分。
請你寫一個程式計算出小明能吃到的蛋糕最高總分為多少分。

範例說明 2:由於無論怎麼拿小明都不喜歡,所以乾脆不拿,輸出 0。
評分說明
此題目測資分成四組,每組測資有多筆測試資料,需答對該組所有測試資料 才能獲得該組分數,各組詳細限制如下。
第一組 (20 分): 1<=N<=10^2,K=1
第二組 (20 分): 1<=N<=10^2
第三組 (10 分): 1<=N<=3 ×10^3
第四組 (50 分): 無特別限制

Input


   第一行有兩個正整數 N (1<=N<=10^5) 和 K (1<=K<=N),
分別表示長方形蛋糕 有 N小塊,小明至多可以拿走相當於 K小塊的連續區段蛋糕。
   接下來一行有 N 個整數,依序代表由左至右每一小塊蛋糕的評分
 Si (|Si|<=100),兩個整數以一個 空白隔開。

Output

請輸出一行整數,表示小明能吃到的蛋糕的最高分,如果完全不拿,輸出 0。

Sample Input #1
7 3 
3 7 -1 9 2 2 1 
Sample Output #1
15
Sample Input #2
5 4 
-3 -4 -5 -6 -7 
Sample Output #2
0
Sample Input #3
10 4 
1 -5 7 2 5 -2 6 3 0 2 
Sample Output #3
14
Sample Input #4
10 5 
10 -3 -5 9 -5 -6 10 7 -20 16
Sample Output #4
17
Sample Input #5
10 5 
10 -3 -5 9 -5 -6 10 7 -20 18
Sample Output #5
18
測資資訊:
記憶體限制: 64 MB
公開 測資點#0 (5%): 1.0s , <1K
公開 測資點#1 (5%): 1.0s , <1K
公開 測資點#2 (5%): 1.0s , <1K
公開 測資點#3 (5%): 1.0s , <1K
公開 測資點#4 (5%): 1.0s , <1K
公開 測資點#5 (5%): 1.0s , <1K
公開 測資點#6 (5%): 1.0s , <1K
公開 測資點#7 (5%): 1.0s , <1K
公開 測資點#8 (5%): 1.0s , <1M
公開 測資點#9 (5%): 1.0s , <1M
公開 測資點#10 (5%): 1.0s , <1M
公開 測資點#11 (5%): 1.0s , <1M
公開 測資點#12 (5%): 1.0s , <1M
公開 測資點#13 (5%): 1.0s , <1M
公開 測資點#14 (5%): 1.0s , <1M
公開 測資點#15 (5%): 1.0s , <1M
公開 測資點#16 (5%): 1.0s , <1M
公開 測資點#17 (5%): 1.0s , <1M
公開 測資點#18 (5%): 1.0s , <1M
公開 測資點#19 (5%): 1.0s , <1M
Hint :
Tags:
前綴和 單調隊列
出處:
TOI練習賽2020年6月潛力組 [管理者:
p3a_owhj (阿普二信)
]


ID User Problem Subject Hit Post Date
22694
yes51851823@... (Wildfire)
f174
15 2020-09-25 22:24