Overview

This problem asks us to divide employees into contiguous groups and maximize the total productivity (number of people × sum of ability values) across all groups.

Analysis

As a naive approach, enumerating all possible partition patterns would require considering \(O(2^N)\) ways to choose partition positions, which is computationally infeasible for \(N=5000\). Therefore, we use dynamic programming (DP). We define DP[r] as the optimal total productivity for employees 1 through r, and perform state transitions by exhaustively searching over the range [l+1, r] of the last group. However, a straightforward implementation would be \(O(N^3)\), requiring approximately 125 billion computations for \(N=5000\), resulting in TLE. To address this, we use prefix sums to reduce each group’s sum calculation to \(O(1)\), speeding up the overall algorithm to \(O(N^2)\).

Algorithm

1. Precompute a prefix sum array prefix_sum, where prefix_sum[i] = \(P_1 + P_2 + \cdots + P_i\).
2. Prepare a DP array and initialize it with DP[0] = 0.
3. Loop r from 1 to N, and for each r, loop l from 0 to r-1:
   • The size of group [l+1, r] is group_size = r - l
   • The sum of ability values in the group is group_sum = prefix_sum[r] - prefix_sum[l]
   • The total productivity when appending this group last is candidate = DP[l] + group_size × group_sum
   • Update DP[r] if candidate is greater than the current DP[r]
4. DP[N] is the desired answer.

Complexity

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

Implementation Notes

• By precomputing prefix sums, partial sum calculations are reduced to \(O(1)\).

• The DP array uses 0-indexed indexing, where DP[r] represents the optimal value for the first r employees.

• Since the inner loop searches l from 0 to r-1, the double loop results in \(O(N^2)\), but for \(N=5000\) this amounts to approximately 12.5 million computations, which is feasible.

  Source Code

import sys

def main():
    data = sys.stdin.read().split()
    n = int(data[0])
    P = list(map(int, data[1:1+n]))
    
    prefix_sum = [0] * (n + 1)
    for i in range(1, n + 1):
        prefix_sum[i] = prefix_sum[i - 1] + P[i - 1]
    
    dp = [0] * (n + 1)
    
    for r in range(1, n + 1):
        dp[r] = dp[r - 1] + P[r - 1]
        for l in range(r):
            group_size = r - l
            group_sum = prefix_sum[r] - prefix_sum[l]
            candidate = dp[l] + group_size * group_sum
            if candidate > dp[r]:
                dp[r] = candidate
                
    print(dp[n])

if __name__ == "__main__":
    main()

This editorial was generated by deepseekv3.