Overview

This problem asks us to divide consecutive employees into groups and maximize the total “productivity” across all groups. Productivity is calculated as “number of people in the group × sum of ability values.”

Analysis

In this problem, we need to partition employees into consecutive intervals, and the goal is to maximize the sum of productivity across all intervals.

A naive approach would be to try all possible combinations of intervals, but this would take exponential time and is impractical. For example, recursively deciding split positions would cause the computation to explode.

Therefore, we consider using dynamic programming (DP).

DP Definition

Define dp[i] as “the maximum total productivity for the first \(i\) people.” The initial value is dp[0] = 0.

To update dp[i], we look at previous states dp[j] (\(0 \leq j < i\)) and compute the productivity when we form a group from the interval \([j+1, i]\).

The productivity of this interval is: $\( \text{productivity} = (i - j) \times \sum_{k=j+1}^{i} P_k \)$

To compute the sum \(\sum P_k\) efficiently, we use prefix sums. Define S[i] as \(P_1 + P_2 + \cdots + P_i\), then the interval sum can be obtained as \(S[i] - S[j]\).

In this way, even if we try all \(j\) for each \(i\), the overall time complexity is \(O(N^2)\), which is sufficiently fast for the constraint \(N \leq 5000\).

Algorithm

1. Read the input and construct the prefix sum array \(S\).
2. Initialize the DP table dp. Set dp[0] = 0, and initialize all others to \(-\infty\).
3. For each \(i = 1, 2, ..., N\), do the following:
   • For each \(j = 0, 1, ..., i-1\), compute the productivity of the interval \([j+1, i]\): $\( \text{productivity} = (i - j) \times (S[i] - S[j]) \)$
   • Update with dp[i] = max(dp[i], dp[j] + productivity).
4. Output dp[N].

Complexity

• Time complexity: \(O(N^2)\)
• Space complexity: \(O(N)\)

Implementation Notes

• Precompute the prefix sums so that interval sums can be calculated efficiently.

• Be careful with the initial values of the DP table: dp[0] = 0, and all others should be initialized to a sufficiently small value (e.g., -float('inf')).

• The length of the interval \([j+1, i]\) is \(i - j\), and the interval sum is \(S[i] - S[j]\).

  Source Code

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    P = list(map(int, data[1:N+1]))
    
    # 累積和を計算
    S = [0] * (N + 1)
    for i in range(N):
        S[i + 1] = S[i] + P[i]
    
    # dp[i] := 最初のi人についての生産性の合計の最大値
    dp = [-float('inf')] * (N + 1)
    dp[0] = 0
    
    for i in range(1, N + 1):
        for j in range(i):
            # 区間[j+1, i]のグループを作る
            length = i - j
            sum_P = S[i] - S[j]
            productivity = length * sum_P
            if dp[j] + productivity > dp[i]:
                dp[i] = dp[j] + productivity
    
    print(dp[N])

if __name__ == "__main__":
    main()

---

This editorial was generated by qwen3-coder-480b.