Problem: Snuke has an integer sequence A of length N.  He will make three cuts in A and divide it into four (non-empty) contiguous subsequences B, C, D and E. The positions of the cuts can be freely chosen.  Let P,Q,R,S be the sums of the elements in B,C,D,E, respectively. Snuke is happier when the absolute difference of the maximum and the minimum among P,Q,R,S is smaller. Find the minimum possible absolute difference of the maximum and the minimum among P,Q,R,S.

Submission attempts (in order):
def S(a, b):
    return cl[b] - (0 if a == 0 else cl[a-1])

def partial(start, end, last):
    odiff = None
    for c in range(start, end+1):
        p = S(start,c)
        q = S(c+1,end)
        diff = abs(p-q)
        if odiff is None:
            odiff = diff
        if odiff < diff:
            return c, mp, mq
        odiff = diff
        mp = p
        mq = q

if __name__ == '__main__':
    # read input
    n = int(input())
    l = list(map(int, input().split()))
    
    cl = list(accumulate(l))
    clen = len(l)

    
    #  |------|------|-------|-------|
    #         c0    c1       c2
    
    # pick up a c1 (i:i+1) and evaluate
    result = None
    c1 = 1
    c3 = 3
    for i in range(1,clen-2):
        # LEFT
        (c1, mb, mc) = partial(0, i, c1)
        # RIGHT
        c3, md, me = partial(i+1, clen-1, c3)

        # evaluate
        diff = abs(max(mb, mc, md, me) - min(mb, mc, md, me))
        if result is None:
            result = diff
        else:
            if result > diff:
                result = diff

    print(result)

from itertools import accumulate

def S(a, b):
    return cl[b] - (0 if a == 0 else cl[a-1])

def partial(start, end, last):
    print("partial: {}-{} last:{}".format(start,end, last))
    last -= 1
    p = S(start, last)
    q = S(last+1, end)
    odiff = abs(p-q)

    for c in range(last, end):
        print("partial c:{}".format(c))
        p = S(start,c)
        q = S(c+1,end)
        diff = abs(p-q)
        if odiff is None:
            odiff = diff
        if odiff < diff:
            return c, mp, mq
        odiff = diff
        mp = p
        mq = q
    return c,mp,mq

if __name__ == '__main__':
    # read input
    n = int(input())
    l = list(map(int, input().split()))
    
    cl = list(accumulate(l))
    clen = len(l)

    
    #  |------|------|-------|-------|
    #         c0    c1       c2
    
    # pick up a c1 (i:i+1) and evaluate
    result = None
    c1 = 1
    c3 = 3
    for i in range(1,clen-2):
        # LEFT
        #print("LEFT: {} RIGHT: {}".format(l[0:i+1], l[i+1: clen]))
        c1, mb, mc = partial(0, i, c1)
        # RIGHT
        c3, md, me = partial(i+1, clen-1, c3)

        #print("{}/{}/{}: [{} {} {} {}]".format(c1, i+1, c3, mb, mc, md, me))

        # evaluate
        diff = abs(max(mb, mc, md, me) - min(mb, mc, md, me))
        if result is None:
            result = diff
        else:
            if result > diff:
                result = diff

    print(result)

from itertools import accumulate

def Sdiff(s, m, e):
    # Sdiff(s, m, e) = [A_s, A_s+1 ..., A_m] [A_m+1 .... A_e]
    #    L = cl[m]-cl[s-1], R = cl[e] - cl[m]
    # diff(L,R) = abs(cl[m] - cl[s-1] - cl[e] + cl[m]) = abs(2*cl[m] - cl[s-1] - cl[e])

    x = 0 if s == 0 else cl[s-1]
    return abs(2*cl[m] - x - cl[e])

def partial(start, end, last):
    
    odiff = Sdiff(start, last, end)

    for c in range(last, end):
        diff = Sdiff(start, c, end)
        
        if odiff < diff:
            return c-1
        odiff = diff
    return c

if __name__ == '__main__':
    # read input
    N = int(input())
    l = list(map(int, input().split()))
    
    cl = list(accumulate(l))

    
    #  |------|------|-------|-------|
    #         c0    c1       c2
    
    # pick up a c1 (i:i+1) and evaluate
    result = 9 * 10e9
    c1 = 0
    c3 = 2
    for i in range(1, N-2):
        #print("LEFT:RIGHT {}/={}=/{}".format(l[0:i+1], i, l[i+1: N]))
        # LEFT
        c1 = partial(0, i, c1)
        # RIGHT
        c3 = partial(i+1, N-1, c3)

        # evaluate
        mb = cl[c1]
        mc = cl[i] - mb
        md = cl[c3] - cl[i]
        me = cl[N-1] - cl[c3]
        diff = abs(max(mb, mc, md, me) - min(mb, mc, md, me))
        #print("\t\t{}/{}/{}: [{} {} {} {}]".format(c1, i, c3, mb, mc, md, me))
        #print("\t\tdiff={}".format(diff))
        if diff < result:
            result = diff

    print(result)

Verdicts: Runtime Error

Wrong Answer

Accepted