from collections import deque
from sys import setrecursionlimit
def compare(s1: list[int], s2: list[int]):
if s1[0] > s2[0]: return True
if s1[0] < s2[0]: return False
if s1[2] < s2[2]: return True
if s1[2] > s2[2]: return False
if s1[1] > s2[1]: return True
if s1[1] < s2[1]: return False
return False
def solve():
n = int(input())
a = list(map(int, input().split(" ")))
prfx = []
prfx.append(a[1])
for i in range(1, n): prfx.append(prfx[-1] + a[i])
def getPrfx(l: int, r: int):
left = 0 if not l else prfx[l-1]
right = prfx[r]
return right - left
memo = [[-1, -1, -1]] * n
def dp(i: int):
if i < 0: return [1, 0, 0]
if memo[i][0] != -1: return memo[i]
res = dp(i-1).copy()
res[2] += a[i]
for j in range(i):
c = dp(j).copy()
s = getPrfx(j+1, i)
# print(s, c[2])
if s < c[2]: continue
c[1] = c[2]
c[2] = s
c[0] += 1
if (compare(c, res)): res = c.copy()
memo[i] = res.copy()
return res
res = dp(n-1)
print(res[0])
"""
"""
solve()
Compilation message (stdout)
Compiling 'segments.py'...
=======
adding: __main__.pyc (deflated 42%)
=======
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |