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 分): 無特別限制
第一行有兩個正整數 N (1<=N<=10^5) 和 K (1<=K<=N),
分別表示長方形蛋糕 有 N小塊,小明至多可以拿走相當於 K小塊的連續區段蛋糕。
接下來一行有 N 個整數,依序代表由左至右每一小塊蛋糕的評分
Si (|Si|<=100),兩個整數以一個 空白隔開。
請輸出一行整數,表示小明能吃到的蛋糕的最高分,如果完全不拿,輸出 0。
7 3 3 7 -1 9 2 2 1
15
5 4 -3 -4 -5 -6 -7
0
10 4 1 -5 7 2 5 -2 6 3 0 2
14
10 5 10 -3 -5 9 -5 -6 10 7 -20 16
17
10 5 10 -3 -5 9 -5 -6 10 7 -20 18
18
ID | User | Problem | Subject | Hit | Post Date |
39644 | toseanlin@gm ... (Dr. SeanXD) | f174 | 189 | 2024-03-16 09:51 | |
36948 | frankleeplay ... (LJH-code) | f174 | 350 | 2023-08-18 09:12 | |
22694 | yes51851823@ ... (wseds) | f174 | 1687 | 2020-09-25 22:24 |