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
公開 測資點#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
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
| 39644 |
|
f174 | 44 | 2024-03-16 09:51 | |
| 36948 |
|
f174 | 231 | 2023-08-18 09:12 | |
| 22694 |
|
f174 | 1507 | 2020-09-25 22:24 |