Overview

This problem asks us to divide \(N\) employees into several contiguous groups and maximize the total sum of “number of people \(\times\) sum of ability values” for each group. By combining prefix sums with dynamic programming (DP), we can solve this efficiently in \(O(N^2)\).

Analysis

For problems where we divide contiguous elements into several intervals and find the optimal score, a one-dimensional dynamic programming (DP) approach is effective, where the state is “the maximum value when dividing the first \(i\) elements.”

First, we use prefix sums to quickly compute the “sum of ability values” within a group. Let \(P\) be the array of employee ability values, and \(S\) be its prefix sum. That is, \(S[i] = \sum_{k=1}^i P_k\). Then, the sum of ability values for the group from employee \(j+1\) to \(i\) can be computed as \(S[i] - S[j]\) in \(O(1)\).

Next, we consider the DP transitions. Define \(dp[i]\) as “the maximum productivity when optimally dividing the first \(i\) employees into groups.” Assuming the last group consists of employees \(j+1\) through \(i\) (containing \(i - j\) people), the productivity of this group is: $\( \text{productivity} = (i - j) \times (S[i] - S[j]) \)$

Therefore, to compute \(dp[i]\), we try all possible positions \(j\) (\(0 \leq j < i\)) for the preceding partition and choose the one that yields the highest score. $\( dp[i] = \max_{0 \leq j < i} \{ dp[j] + (i - j) \times (S[i] - S[j]) \} \)$

Since there are \(N\) states and the transition for each state (searching over \(j\)) is \(O(N)\), the overall time complexity is \(O(N^2)\). Under the constraint \(N \leq 5000\), an \(O(N^2)\) algorithm is sufficient to fit within the time limit.

Algorithm

1. Build the prefix sum Create the prefix sum array \(S\) of ability values \(P\). Set \(S[0] = 0\) and compute \(S[i] = S[i-1] + P_{i-1}\).
2. Initialize the DP array Prepare a \(dp\) array of length \(N+1\) and initialize it with \(0\).
3. DP transitions For \(i = 1, 2, \ldots, N\), compute the following: $\( dp[i] = \max_{0 \leq j < i} \{ dp[j] + (i - j) \times (S[i] - S[j]) \} \)$
4. Output the answer The final answer is stored in \(dp[N]\).

Complexity

• Time complexity: \(O(N^2)\) For each of the \(N\) states, we compute up to \(N\) transitions.
• Space complexity: \(O(N)\) We use memory proportional to \(N\) to store the prefix sum array \(S\), the DP array \(dp\), and related data.

Implementation Notes

If you naively implement the \(O(N^2)\) nested loop in a scripting language like Python, the constant factor can be large enough to cause a Time Limit Exceeded (TLE) verdict. To address this, it is effective to expand the formula and reduce the computation inside the loop.

Expanding the transition formula gives: $\( (i - j) \times (S[i] - S[j]) = i \cdot S[i] - i \cdot S[j] - j \cdot S[i] + j \cdot S[j] \)$

Here, \(i \cdot S[i]\) does not depend on \(j\), so it can be factored out of the \(\max\). $\( dp[i] = \max_{0 \leq j < i} \{ (dp[j] + j \cdot S[j]) - i \cdot S[j] - S[i] \cdot j \} + i \cdot S[i] \)$

In the implementation, by precomputing and storing \(A[j] = dp[j] + j \cdot S[j]\) as an array, we minimize the computation inside the loop. Furthermore, by using Python’s list comprehension and the built-in max() function, the loop processing is executed at C-level speed, allowing us to safely pass within the time limit.

Source Code

import sys

def solve():
    input = sys.stdin.read
    data = input().split()
    if not data:
        return
    N = int(data[0])
    P = [int(x) for x in data[1:]]
    
    S = [0] * (N + 1)
    for i in range(N):
        S[i+1] = S[i] + P[i]
        
    dp = [0] * (N + 1)
    A = [0] * (N + 1)
    B = S
    
    for i in range(1, N + 1):
        Si = B[i]
        dp_i = max([A[j] - i * B[j] - Si * j for j in range(i)]) + i * Si
        dp[i] = dp_i
        A[i] = dp_i + i * Si
        
    print(dp[N])

if __name__ == '__main__':
    solve()

---

This editorial was generated by gemini-3.1-pro-thinking.