T324390 冰与火之歌

 $$ 莫倚偎我\ 我习于冷 $$ $$ 志于成冰\ 莫倚偎我 $$ $$ 别走近我\ 我正升焰 $$ $$ 万木俱焚\ 别走近我 $$

在末日，世界的尽头，有 $n$ 个基地来保护渺小的人类。众所周知温度对于生命来说至关重要，所以每一个基地都有相应的原本温度 $t_i$，现有 $m$ 个人类，要被分配到基地中试图存活，定义体感温度 $temp_i$，基地中人数 $x_i$，则有 $temp_i=t_i-x+1$，求一种分配方法使每个人类的体感温度和加在一起最大，这样他们才有机会活命。（$x$ 以分配完后为准） **简化题意** 给定 $n,m$ 和一个长为 $n$ 的序列 $\left\{t_i\right\}$，请你构造一个长为 $n$ 的序列 $\left\{x_i\right\}$ 满足： $$\sum_{i=1}^n x_i=m$$ 并最大化： $$\sum_{i=1}^n x_i(t_i-x_i+1)$$ 并输出这个答案。

第一行两个整数 $n,m$； 第二行 $n$ 个整数 $t_i$。

一个整数表示答案。

**样例解释** 对于样例 $1$，唯一的最优方案是在第一个基地分配 $3$ 个人，第二个分配 $0$ 个人，总体感温度 $3\times(10-(3-1))+0\times(5-(0-1))=24$。 对于样例 $2$，一种最优方案是在第一个基地分配 $4$ 个人，第二个分配 $2$ 个人，总体感温度 $4\times(10-(4-1))+2\times(5-(2-1))=36$。 对于样例 $3$，该样例满足 $\text{Subtask3}$ 的要求。 --- **数据范围** **提示：本题采用捆绑计分。** | 子任务编号 | 分值 | 约束 | | :-: | :-: | :-: | | 1 | 10 | $1\leq n,m\leq8$ | | 2 | 30 | $1\leq n,m\leq10^4$ | | 3 | 60 | 无 | 对于 $100\%$ 的数据，保证 $1 \leq n,m \leq 4\times10^5$，$1\leq t_i \leq 10^9 $。 --- **题目来源** | 项目 | 人员 | |:-:|:-:| | idea | ztntonny | | data | lyhqwq | | check | Zhang_bingjia | | solution | Zhang_bingjia | | std | ztntonny |