a144. TOI 2021/04 潛力組：遊戲升等

題目描述

軍團有 N 位士兵，原本等級為 a[i]。把一位士兵從 a[i] 提升到 U，若 U > a[i]，需花費 (U − a[i])² 枚金幣；原本已達 U 級的人不需升等。你共有 C 枚金幣，請求出能使所有士兵都至少達到的最高等級。

輸入格式

第一行為 N、C，第二行為 N 個初始等級。 1 ≤ N ≤ 20000；1 ≤ C ≤ 100000000000000；1 ≤ a[i] ≤ 10000000。

輸出格式

輸出可達成的最高共同最低等級 U。

來源

TOI 2021/04/26~2021/04/30 潛力組〈遊戲升等〉。本題以自寫文字重述規則，範例與測資另行設計。 https://tpmso.k12ea.gov.tw/toi/wp-content/uploads/question/202104/Game.pdf