Submission #1204965

#	Time	Username	Problem	Language	Result	Execution time	Memory
1204965		ofoz	Bigger segments (IZhO19_segments)	Pypy 3	37 / 100	560 ms	75056 KiB

segments

from collections import deque
from sys import setrecursionlimit
setrecursionlimit(int(3e3))
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%)

=======

• Subtask 1: 13 / 13
• Subtask 2: 14 / 14
• Subtask 3: 10 / 10
• Subtask 4: 0 / 36
• Subtask 5: 0 / 27