Submission #1204720

#	Time	Username	Problem	Language	Result	Execution time	Memory
1204720		ofoz	Bigger segments (IZhO19_segments)	Pypy 3	0 / 100	974 ms	56468 KiB

segments

from collections import deque
from sys import setrecursionlimit

def isHigher(c1: list[int], c2: list[int]):
    if any([x < 0 for x in c1]): return False
    if any([x < 0 for x in c2]): return True
    if c1[0] < c2[0]: return True
    return False


def solve():
    
    n = int(input())
    a = list(map(int, input().split(" ")))
    def dp(i: int, seg: int): # (mn sum, completed segments, current sum)
        if i < 0: return [-float('inf')] * 3 if seg else [0] * 3
        if i+1 < seg or not seg: return [-float('inf')] * 3
        c1 = dp(i-1, seg)
        c2 = dp(i-1, seg-1)
        
        c1[2] += a[i]
        
        if c2[2] < c2[0]: return c1

        c2[0] = c2[2]
        c2[2] = a[i]
        c2[1] += 1

        if isHigher(c1, c2): return c1
        return c2
    


    res = -1
    for seg in range(1, n+1):
        cur = dp(n-1, seg)
        # print(cur)
        if cur[1] < seg: continue
        # print(cur)
        res = max(res, cur[1])


    print(res)

        


"""
A_i <= A_i+1
"""




solve()

Compilation message (stdout)

Compiling 'segments.py'...

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

=======

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