a248. TOI 2026/05 新手組：礦業調度

題目描述

共有 N 個礦點，編號為 1 到 N。第 i 個礦點第一次開採時可取得 Aᵢ 單位金礦。從第一次開採起，該礦點的每日產量逐日減少 1：隔天為 Aᵢ − 1，再隔天為 Aᵢ − 2，依此類推。尚未開始開採的礦點，初始產量不會減少。

每天最多選擇一個礦點開採。當天若開採第 i 個礦點，需要從當天取得的金礦中支付 i − 1 單位運輸費，因此當天淨收益為產量減去運輸費。不再有能帶來正收益的礦點時就停止。

你可以自行安排開採順序。請求出未來 M 天內能取得的最大金礦淨收益。

輸入格式

第一行輸入兩個整數 N、M。 第二行輸入 N 個整數 A₁、A₂、…、Aₙ，依序表示各礦點的初始產量。

• 1 ≤ N ≤ 100000
• 1 ≤ M ≤ 100
• 1 ≤ Aᵢ ≤ 1000000

輸出格式

輸出一個整數，表示 M 天內可以取得的最大總淨收益。

來源

TOI 2026 年 5 月新手組〈礦業調度〉，題目敘述重新撰寫，範例與測資另行設計。 https://tpmso.k12ea.gov.tw/toi/wp-content/uploads/question/202605/Mining.pdf