a120. TOI 2022/11 潛力組：販售蔬果

題目描述

鄉鎮依序編號為 1 到 N，相鄰兩鎮距離為 1。農夫從鄉鎮 1 出發，沿編號增加方向行駛到鄉鎮 N，不能往回開。

農夫可以選擇在中間的鄉鎮停靠販售蔬果；在鄉鎮 i 停留一天可獲得 Pi 的淨利，Pi 可能為負，每鎮最多停留一天。

貨車加滿油最多能行駛 D 單位距離。出發時油箱已滿，每次停靠後也會重新加滿，所以任意兩次連續停靠之間的距離不得超過 D，起點與終點也算停靠點，但不產生收益。

請選擇停靠地點，使能夠到達終點的總收益最大。

輸入格式

第一行輸入 N、D，4 ≤ N ≤ 200000，1 ≤ D ≤ N。 第二行有 N−2 個整數，依序為 P2 到 PN−1，−1000 ≤ Pi ≤ 1000。

輸出格式

輸出完成旅程能獲得的最大總收益。收益可能為負。

來源

TOI 2022 年 11 月潛力組〈販售蔬果〉。依官方題意重新撰寫，範例與測資另行設計。 https://tpmso.k12ea.gov.tw/toi/wp-content/uploads/question/202211/Selling.pdf