7162. [GESP202606 五级] 排排坐
时间限制：1000 MS 内存限制：256 MB
题目描述
## 题目描述 老师正在和小朋友们分糖果。 小朋友们先在自己的手上写一个数字，然后坐成一排。 老师分发糖果的规则是：每个小朋友获得自己以及左侧所有小朋友的手上数字之和个糖果。 现在小朋友们都已经在自己手上写上了数字。 请帮小朋友们安排合适的座位顺序，使得小朋友们分到的糖果总量最大，输出这个最大值。 ## 输入格式 输入 $2$ 行， 第一行为一个正整数 $n$，表示小朋友的个数； 第二行为 $n$ 个正整数 $a_1, a_2, \cdots, a_n$，表示小朋友们手上的数字，整数之间以空格分隔。 ## 输出格式 输出一个整数，表示小朋友们可能分到的最大糖果总数量。 ## 输入输出样例 #1 ### 输入 #1 ``` 5 7 5 8 9 3 ``` ### 输出 #1 ``` 111 ``` ## 说明/提示 ### 样例解释 小朋友安排座位后从左向右每人手上数字依次是：$9, 8, 7, 5, 3$。 这时可以得到最多的糖果：$(9) + (9 + 8) + (9 + 8 + 7) + (9 + 8 + 7 + 5) + (9 + 8 + 7 + 5 + 3) = 111$。 ### 数据范围 $1 \le n \le 1000$，$1 \le a_i \le 1000$。