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):
# -*- coding: utf-8 -*-
def two_pointers(ary, l, r, split, ary_func, comb_func, comp_func):
    '''
    This function is supposed to be repeatedly called so that 'split' keeps
    renewing, under an assumption that 'split' increases monotonously.
    ('l' and 'r' just specify the region to be searched in 'ary')
    '''

    left = ary_func(ary, l, split)
    right = ary_func(ary, split, r)
    val = comb_func(left, right)

    for i in range(split + 1, r):
        tmp_left = ary_func(ary, l, i)
        tmp_right = ary_func(ary, i, r)
        tmp_val = comb_func(tmp_left, tmp_right)

        if comp_func(val, tmp_val):
            return i - 1, val, left, right
        else:
            left = tmp_left
            right = tmp_right
            val = tmp_val

    else:
        return r - 1, val, left, right


if __name__ == '__main__':
    from operator import add
    from itertools import accumulate

    n = int(input())
    a = [int(_) for _ in input().split()]
    cul_ary = [0] + list(accumulate(a, add))

    l_split = 1
    r_split = 3
    griefs = []
    for i in range(2, n - 1):
        # left
        l_split, l_diff, p, q = two_pointers(cul_ary,
                                             0,
                                             i,
                                             l_split,
                                             lambda ary, l, r: ary[r] - ary[l],
                                             lambda left, right: abs(left - right),
                                             lambda val1, val2: True if val1 > val2 else False)

        # right
        r_split, r_diff, r, s = two_pointers(cul_ary,
                                             i,
                                             n,
                                             r_split,
                                             lambda ary, l, r: ary[r] - ary[l],
                                             lambda left, right: abs(left - right),
                                             lambda val1, val2: True if val1 > val2 else False)

        griefs.append(max(p, q, r, s) - min(p, q, r, s))

    print(min(griefs))


# -*- coding: utf-8 -*-
n = int(input())
a = [int(_) for _ in input().split()]

# my initial trial below ##############################
# from itertools import combinations
# INF = 10 ** 15
# combs = combinations(range(1, n), 3)
# grief = INF
# for comb in combs:
#     p = sum(a[:comb[0]])

#     r = sum(a[comb[1]:comb[2]])



#     if tmp < grief:
#         grief = tmp



# solution below ######################################
INF = 10**15
cumul_sum = [0]
for i, ai in enumerate(a):
    cumul_sum.append(ai + cumul_sum[i])


def cal_sum(left, right):
    return cumul_sum[right] - cumul_sum[left]


def two_pointers(l, r, split, diff):
    left_sum = cal_sum(l, split)
    right_sum = cal_sum(split, r)

    for i in range(split, r):
        tmp_left_sum = cal_sum(l, i)
        tmp_right_sum = cal_sum(i, r)
        tmp_diff = abs(left_sum - right_sum)

        if diff >= tmp_diff:
            left_sum = tmp_left_sum
            right_sum = tmp_right_sum
            diff = tmp_diff
        else:
            return i - 1, diff, left_sum, right_sum
    else:
        return r - 1, diff, left_sum, right_sum


l_split = 1
r_split = 3
griefs = []
for i in range(2, n - 1):
    # left
    l_split, l_diff, p, q = two_pointers(0, i, l_split, INF)
    # right
    r_split, r_diff, r, s = two_pointers(i, n, r_split, INF)
    griefs.append(max(p, q, r, s) - min(p, q, r, s))

print(min(griefs))


# -*- coding: utf-8 -*-
from scratch import two_pointers
from operator import add, lt
from itertools import accumulate

n = int(input())
a = [int(_) for _ in input().split()]
cul_ary = [0] + list(accumulate(a, add))

l_split = 1
r_split = 3
griefs = []

for i in range(2, n - 1):
    l_split, l_diff, p, q = two_pointers(cul_ary,
                                         0,
                                         i,
                                         l_split,
                                         lambda ary, l, r: ary[r] - ary[l],
                                         lambda left, right: abs(left - right),
                                         lambda val1, val2: True if val1 > val2 else False)

    r_split, r_diff, r, s = two_pointers(cul_ary,
                                         i,
                                         n,
                                         r_split,
                                         lambda ary, l, r: ary[r] - ary[l],
                                         lambda left, right: abs(left - right),
                                         lambda val1, val2: True if val1 > val2 else False)

    griefs.append(max(p, q, r, s) - min(p, q, r, s))

print(min(griefs))


# -*- coding: utf-8 -*-
n = int(input())
a = [int(_) for _ in input().split()]

# my initial trial below ##############################
# from itertools import combinations
# INF = 10 ** 15
# combs = combinations(range(1, n), 3)
# grief = INF
# for comb in combs:
#     p = sum(a[:comb[0]])

#     r = sum(a[comb[1]:comb[2]])



#     if tmp < grief:
#         grief = tmp



# solution below ######################################
INF = 10**15
cumul_sum = [0]
for i, ai in enumerate(a):
    cumul_sum.append(ai + cumul_sum[i])


def cal_sum(left, right):
    return cumul_sum[right] - cumul_sum[left]


def two_pointers(l, r, split, diff):
    left_sum = cal_sum(l, split)
    right_sum = cal_sum(split, r)

    for i in range(split, r):
        tmp_left_sum = cal_sum(l, i)
        tmp_right_sum = cal_sum(i, r)
        tmp_diff = abs(left_sum - right_sum)

        if diff >= tmp_diff:
            left_sum = tmp_left_sum
            right_sum = tmp_right_sum
            diff = tmp_diff
        else:
            return i - 1, diff, left_sum, right_sum
    else:
        return r - 1, diff, tmp_left_sum, tmp_right_sum


l_split = 1
r_split = 3
griefs = []
for i in range(2, n - 1):
    # left
    l_split, l_diff, p, q = two_pointers(0, i, l_split, INF)
    # right
    r_split, r_diff, r, s = two_pointers(i, n, r_split, INF)
    griefs.append(max(p, q, r, s) - min(p, q, r, s))

print(min(griefs))


# -*- coding: utf-8 -*-
from itertools import accumulate


def two_pointers(ary, l, r, split, ary_func, comb_func, comp_func):
    '''
    This function is supposed to be repeatedly called so that 'split' keeps
    renewing, under an assumption that 'split' increases monotonously.
    ('l' and 'r' just specify the region to be searched in 'ary')
    '''

    left = ary_func(ary, l, split)
    right = ary_func(ary, split, r)
    val = comb_func(left, right)

    for i in range(split + 1, r):
        tmp_left = ary_func(ary, l, i)
        tmp_right = ary_func(ary, i, r)
        tmp_val = comb_func(tmp_left, tmp_right)

        if comp_func(val, tmp_val):
            return i - 1, val, left, right
        else:
            left = tmp_left
            right = tmp_right
            val = tmp_val

    else:
        return r - 1, val, left, right


if __name__ == '__main__':
    n = int(input())
    a = [int(_) for _ in input().split()]
    cul_ary = [0] + list(accumulate(a))

    l_split = 1
    r_split = 3
    griefs = []

    for i in range(2, n - 1):
        l_split, l_diff, p, q = two_pointers(
            cul_ary, 0, i, l_split, lambda ary, l, r: ary[r] - ary[l],
            lambda left, right: abs(left - right),
            lambda val1, val2: True if val1 > val2 else False)

        r_split, r_diff, r, s = two_pointers(
            cul_ary, i, n, r_split, lambda ary, l, r: ary[r] - ary[l],
            lambda left, right: abs(left - right),
            lambda val1, val2: True if val1 > val2 else False)

        griefs.append(max(p, q, r, s) - min(p, q, r, s))

    print(min(griefs))


# -*- coding: utf-8 -*-
def two_pointers(ary, l, r, split, ary_func, comb_func, comp_func):
    '''
    This function is supposed to be repeatedly called so that 'split' keeps
    renewing, under an assumption that 'split' increases monotonously.
    ('l' and 'r' just specify the region to be searched in 'ary')
    '''

    left = ary_func(ary, l, split)
    right = ary_func(ary, split, r)
    val = comb_func(left, right)

    for i in range(split + 1, r):
        tmp_left = ary_func(ary, l, i)
        tmp_right = ary_func(ary, i, r)
        tmp_val = comb_func(tmp_left, tmp_right)

        if comp_func(val, tmp_val):
            return i - 1, val, left, right
        else:
            left = tmp_left
            right = tmp_right
            val = tmp_val

    else:
        return r - 1, val, left, right


if __name__ == '__main__':
    '''
    an example of using this function
    At-Coder ABC 102 - D
    '''

    from operator import add
    from itertools import accumulate

    n = int(input())
    a = [int(_) for _ in input().split()]
    cul_ary = [0] + list(accumulate(a, add))

    l_split = 1
    r_split = 3
    funcs = (lambda ary, l, r: ary[r] - ary[l],
             lambda left, right: abs(left - right),
             lambda val1, val2: True if val1 < val2 else False)
    griefs = []
    for i in range(2, n - 1):
        # left
        l_split, l_diff, p, q = two_pointers(cul_ary, 0, i, l_split, *funcs)

        # right
        r_split, r_diff, r, s = two_pointers(cul_ary, i, n, r_split, *funcs)

        griefs.append(max(p, q, r, s) - min(p, q, r, s))

    print(min(griefs))


Verdicts: Wrong Answer

Wrong Answer

Runtime Error

Wrong Answer

Wrong Answer

Accepted