1
# Runtime: 6408 ms (Top 13.33%) | Memory: 26.1 MB (Top 43.33%)
2
from collections import defaultdict
3
from itertools import accumulate
4

5

6
class Solution:
7

8
    def stoneGameV(self, stoneValue: List[int]) -> int:
9
        n = len(stoneValue)
10
        dp = [[0] * n for _ in range(n)]
11
        left = [[0] * n for _ in range(n)]
12
        prefix = list(accumulate(stoneValue))
13
        prefix = [0] + prefix + [prefix[-1]]
14

15
        def sum(i, j):
16
            return prefix[j + 1] - prefix[i]
17

18
        row_idx = [i for i in range(n)]
19
        for i in range(n):
20
            left[i][i] = stoneValue[i]
21
        for d in range(1, n):
22
            for i in range(n - d):
23
                j = i + d
24
                while sum(i, row_idx[i]) < sum(row_idx[i] + 1, j):
25
                    row_idx[i] += 1
26
                if sum(i, row_idx[i]) == sum(row_idx[i] + 1, j):
27
                    dp[i][j] = max(left[i][row_idx[i]], left[j][row_idx[i] + 1])
28
                else:
29
                    if row_idx[i] == i:
30
                        dp[i][j] = left[j][i + 1]
31
                    elif row_idx[i] == j:
32
                        dp[i][j] = left[i][j - 1]
33
                    else:
34
                        dp[i][j] = max(left[i][row_idx[i] - 1], left[j][row_idx[i] + 1])
35
                left[j][i] = max(left[j][i + 1], sum(i, j) + dp[i][j])
36
                left[i][j] = max(left[i][j - 1], sum(i, j) + dp[i][j])
37
        return dp[0][n - 1]