Submission #1204825

#	Time	Username	Problem	Language	Result	Execution time	Memory
1204825		ofoz	Bigger segments (IZhO19_segments)	Pypy 3	13 / 100	1596 ms	82992 KiB

segments

from collections import deque
from sys import setrecursionlimit

def solve():
    n = int(input())
    a = list(map(int, input().split(" ")))
    a.insert(0, -1) # maintain one-indexed
    prfx = []
    prfx.append(-1)
    prfx.append(a[1])
    for i in range(2, n+1): 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
    
    dp = [[[float('inf'), float('inf')] for _ in range(n+1)] for _ in range(n+1)]
    dp[0][0] = [0, 0]
    cur = 0
    for i in range(1, n+1):
        cur += a[i]
        dp[i][1] = [0, cur]

    for i in range(1, n+1):
        for s in range(2, i+1):
            dp[i][s] = dp[i-1][s].copy()
            dp[i][s][1] += a[i]

            for j in range(1, i):
                
                cur = getPrfx(j+1, i)
                
                if dp[j][s-1][1] <= cur:
                    c = dp[j][s-1].copy()
                    c[0] = c[1]
                    c[1] = cur
                    dp[i][s] = min(dp[i][s], c, key = lambda p: list(reversed(p)))




    
    for seg in range(n, 0, -1):
        if dp[n][seg] != [float('inf'), float('inf')]:
            print(seg)
            return
    print(1)





        


"""
let dp[i][seg] denote (mn, cur), where, if we have seg segments up to the i-th point, mn is the minimum sum and cur is the current sum.
it follows that they should always be minimal.

"""




solve()

Compilation message (stdout)

Compiling 'segments.py'...

=======
  adding: __main__.pyc (deflated 44%)

=======

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