a315. TOI 2022/01 潛力組：一二三木頭人

題目描述

一場遊戲持續 N 個時刻，第 i 個時刻的價值為 mi。你可以選擇若干段連續時刻進行「回頭」。每一段長度不能超過 T；相鄰兩段之間，至少要有 K 個沒有回頭的時刻。第一段之前與最後一段之後不受間隔限制。

總得分是所有回頭時刻的價值總和。請求出符合規則的最大總得分。

輸入格式

第一行是 N、K、T，第二行是 N 個價值。

• 1 ≤ N ≤ 4000000
• 1 ≤ K、T ≤ N
• 0 ≤ mi ≤ 1000000000

輸出格式

輸出最大總得分，使用足以保存答案的整數型別。

來源

TOI 2021 年 12 月題組〈一二三木頭人〉，賽期為 2022 年 1 月。以自寫文字重述，範例與測資另行設計。 https://tpmso.k12ea.gov.tw/toi/wp-content/uploads/question/202112/Freeze.pdf 題意核對鏡像：https://zerojudge.tw/ShowProblem?problemid=h065