Overview

This problem asks us to divide employees (in order by number) into several contiguous intervals (groups) and maximize the total productivity, where each group’s productivity is \((size) \times (sum\ of\ abilities)\). We find the maximum value using interval DP.

Analysis

Key Insight

• Since groups consist of “consecutive employees,” a partition is determined solely by “where to place the boundaries.”
• In other words, if we know the optimal solution for employees \(1..r\), we can construct the optimal solution for \(1..r\) by exhaustively searching over where the last interval begins (i.e., \(l+1..r\)).

Why the Naive Approach Fails

If we choose “cut/don’t cut” for each boundary (\(N-1\) of them), there are \(2^{N-1}\) possible partitions, which is far too many to enumerate when \(N \le 5000\) (TLE).

How to Solve It

We use a DP that maintains “the optimal value from the beginning.” The sum of abilities over an interval can be computed in \(O(1)\) using prefix sums, keeping the transition to \(O(N^2)\). For \(N=5000\), this amounts to roughly \(25{,}000{,}000\) operations, which is fast enough.

Algorithm

1. Prefix Sums

Define the prefix sum \(S\) of ability values as: - \(S[0]=0\) - \(S[i]=\sum_{t=1}^{i} P_t\)

Then the sum of abilities over the interval \([l+1, r]\) is: $\(\sum_{i=l+1}^{r} P_i = S[r]-S[l]\)\( which can be computed in \)O(1)$.

2. DP Definition

\[dp[r] = \text{maximum total productivity when partitioning employees }1..r\]

The answer is \(dp[N]\).

3. Transition

If the last group consists of employees \(l+1..r\) (\(0 \le l < r\)), then: - The group size is \((r-l)\) - The sum of abilities is \((S[r]-S[l])\)

So the productivity of that group is: $\((r-l)\times (S[r]-S[l])\)$

Therefore, the transition is: $\(dp[r] = \max_{0\le l<r}\left(dp[l] + (r-l)\times (S[r]-S[l])\right)\)$

4. Small Example

For example, when \(P=[3,-2,4]\): - All in one group: size \(3\), sum \(5\) → \(3\times 5=15\) - \([3]\) and \([-2,4]\): \(1\times 3 + 2\times 2 = 3+4=7\) - \([3,-2]\) and \([4]\): \(2\times 1 + 1\times 4 = 2+4=6\) - All separate: \(1\times 3 + 1\times(-2) + 1\times 4 = 5\)

The maximum is \(15\), and the DP correctly selects this (it simply evaluates intervals as-is, even those with negative ability sums, and maximizes).

Complexity

• Time complexity: \(O(N^2)\) (for each \(r\), we exhaustively search over \(l\))
• Space complexity: \(O(N)\) (prefix sum array \(S\) and DP array)

Implementation Notes

• We use prefix sums \(S\) to quickly compute the interval sums needed in the transition (\(S[r]-S[l]\)).

• For \(dp[r]\), we exhaustively search over all possible starting points \(l+1\) of the last interval and take the maximum.

• In Python, \(O(N^2)\) can be tight, so the code includes the following constant-factor optimizations:

  • Fast input using sys.stdin.buffer.read()

  • Storing references in local variables like dp_local and S_local to speed up access

  • Instead of computing length = r-l each iteration, decrementing length incrementally within the loop

    Source Code

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    N = data[0]
    P = data[1:]

    S = [0] * (N + 1)
    for i in range(N):
        S[i + 1] = S[i] + P[i]

    dp = [0] * (N + 1)
    NEG = -10**30

    dp_local = dp
    S_local = S

    for r in range(1, N + 1):
        Sr = S_local[r]
        best = NEG
        length = r
        for l in range(r):
            val = dp_local[l] + length * (Sr - S_local[l])
            if val > best:
                best = val
            length -= 1
        dp_local[r] = best

    print(dp_local[N])

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.