/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 400 点
問題文
高橋君は、N 人の社員を管理するプロジェクトリーダーです。
N 人の社員には社員 1, 2, \ldots, N と番号がついています。各社員 i（1 \leq i \leq N）には「能力値」 P_i が設定されています。能力値は負の値をとることもあります。
高橋君はこの N 人の社員を、1 つ以上 N 個以下のグループに分割します。各グループは番号が連続する社員からなり、すべての社員がちょうど 1 つのグループに属するようにします。すなわち、あるグループ数 k（1 \leq k \leq N）と 0 = c_0 < c_1 < \cdots < c_k = N を満たす整数列 c_0, c_1, \ldots, c_k が存在して、第 j グループ（1 \leq j \leq k）が社員 c_{j-1}+1, c_{j-1}+2, \ldots, c_j からなるような分割を考えます。N 人全員を 1 つのグループにすることも、各社員をそれぞれ単独のグループにすることも許されます。
チームワークの効果により、グループの人数が多いほど相乗効果が生まれます。具体的には、社員 l, l+1, \ldots, r（1 \leq l \leq r \leq N）からなるグループの生産性は次の式で計算されます。
\text{生産性} = (r - l + 1) \times \sum_{i=l}^{r} P_i
ここで (r - l + 1) はグループの人数、\displaystyle\sum_{i=l}^{r} P_i はグループ内の能力値の合計です。グループ内の能力値の合計が負の場合、そのグループの生産性も負になることに注意してください。
高橋君は、すべてのグループの生産性の合計を最大化するように分割を決めたいです。生産性の合計の最大値を求めてください。
制約
- 1 \leq N \leq 5000
- -10^6 \leq P_i \leq 10^6（1 \leq i \leq N）
- 入力はすべて整数である。
- 生産性の合計の最大値は 64 ビット符号付き整数型に収まる。
入力
N P_1 P_2 \ldots P_N
- 1 行目には、社員の人数を表す整数 N が与えられる。
- 2 行目には、各社員の能力値を表す N 個の整数 P_1, P_2, \ldots, P_N がスペース区切りで与えられる。
出力
生産性の合計の最大値を整数として 1 行で出力せよ。
入力例 1
3 1 2 3
出力例 1
18
入力例 2
4 3 -5 -5 3
出力例 2
-4
入力例 3
8 2 -1 3 -2 4 1 -3 5
出力例 3
72
入力例 4
15 10 -3 5 8 -12 7 2 -1 6 -4 3 9 -8 11 4
出力例 4
555
入力例 5
1 -1000000
出力例 5
-1000000
Score : 400 pts
Problem Statement
Takahashi is a project leader managing N employees.
The N employees are numbered employee 1, 2, \ldots, N. Each employee i (1 \leq i \leq N) has an "ability value" P_i. Ability values can be negative.
Takahashi will divide these N employees into at least 1 and at most N groups. Each group consists of employees with consecutive numbers, and every employee belongs to exactly one group. Specifically, we consider a partition where there exists some number of groups k (1 \leq k \leq N) and an integer sequence c_0, c_1, \ldots, c_k satisfying 0 = c_0 < c_1 < \cdots < c_k = N, such that the j-th group (1 \leq j \leq k) consists of employees c_{j-1}+1, c_{j-1}+2, \ldots, c_j. It is allowed to place all N employees into a single group, or to place each employee into their own individual group.
Due to the effect of teamwork, larger groups produce greater synergy. Specifically, the productivity of a group consisting of employees l, l+1, \ldots, r (1 \leq l \leq r \leq N) is calculated by the following formula:
\text{productivity} = (r - l + 1) \times \sum_{i=l}^{r} P_i
Here, (r - l + 1) is the number of people in the group, and \displaystyle\sum_{i=l}^{r} P_i is the sum of ability values within the group. Note that if the sum of ability values within a group is negative, the productivity of that group is also negative.
Takahashi wants to determine the partition that maximizes the total productivity across all groups. Find the maximum value of the total productivity.
Constraints
- 1 \leq N \leq 5000
- -10^6 \leq P_i \leq 10^6 (1 \leq i \leq N)
- All inputs are integers.
- The maximum value of the total productivity fits in a 64-bit signed integer type.
Input
N P_1 P_2 \ldots P_N
- The first line contains an integer N representing the number of employees.
- The second line contains N integers P_1, P_2, \ldots, P_N representing the ability values of each employee, separated by spaces.
Output
Output the maximum value of the total productivity as an integer on a single line.
Sample Input 1
3 1 2 3
Sample Output 1
18
Sample Input 2
4 3 -5 -5 3
Sample Output 2
-4
Sample Input 3
8 2 -1 3 -2 4 1 -3 5
Sample Output 3
72
Sample Input 4
15 10 -3 5 8 -12 7 2 -1 6 -4 3 9 -8 11 4
Sample Output 4
555
Sample Input 5
1 -1000000
Sample Output 5
-1000000