Submission #1204406

#	Time	Username	Problem	Language	Result	Execution time	Memory
1204406		ofoz	Bigger segments (IZhO19_segments)	Pypy 3	0 / 100	140 ms	48820 KiB

segments

from collections import deque
from sys import setrecursionlimit


def solve():
    n = int(input())
    a = list(map(int, input().split(" ")))
    curRight = 0
    res = 1
    for i in range(n-1, -1, -1):
        curLeft = 0
        curRight += a[i]
        for j in range(i):
            curLeft += a[j]
            if curLeft > curRight: continue
            cur = 0
            seg = 2
            prv = curLeft
            for k in range(j+1, i):
                cur += a[k]
                if cur > curRight:
                    seg = -1
                    break

                if cur > prv:
                    seg += 1
                    prv = cur
                    cur = 0
                    

            res = max(res, seg)
    print(res)





"""
let mx[i] denote the maximum number of segments you can create up to the i-th point.
let cur[i] denote, out of all these maximum numbers of segments, the lowest ending sum of them all.
"""





solve()

Compilation message (stdout)

Compiling 'segments.py'...

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

=======

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