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 -*-
import sys
import copy
import collections
from bisect import bisect_left
from bisect import bisect_right
from collections import defaultdict
from heapq import heappop, heappush
import numpy as np
import statistics
from statistics import mean, median,variance,stdev
import math

def main():
	N = int(input())
	A = list(map(int, input().split(" ")))
	
	a_sum = []
	for i, val in enumerate(A):
		if i == 0:
			a_sum.append(val)
			continue
		a_sum.append(val + a_sum[i-1])
		
	ans = -1
	for i in range(2, N-1):
		L = A[:i]
		L_sum = a_sum[:i]
		R = A[i:]
		R_sum = a_sum[i:]
		
		# L
		End = L_sum[-1]
		Start = L_sum[0]
		Half = End // 2
		L_part = bisect_right(L_sum, Half)
		if L_part == 0:
			L_part += 1
		
		if len(L_sum) != 2:
			if L_part == 1:
				a = End - L_sum[L_part-1]
				b = End - L_sum[L_part]
				
				if b <= a:
					L_part += 1
			elif L_part == len(L_sum)-1:
				a = End - L_sum[L_part-1]
				b = End - L_sum[L_part-2]
				
				if b <= a:
					L_part -= 1
			else:
				a = End - L_sum[L_part-1]
				b = End - L_sum[L_part-2]
				c = End - L_sum[L_part]
				
				if b <= a and b <= c:
					L_part += 1
				elif c <= a and c <= b:
					L_part -= 1
		
		# R
		End = R_sum[-1]
		Start = R_sum[0]
		Half = End // 2
		R_part = bisect_right(R_sum, Half)
		if R_part == 0:
			R_part += 1
		
		if len(R_sum) != 2:
			if R_part == 1:
				a = End - R_sum[R_part-1]
				b = End - R_sum[R_part]
				
				if b <= a:
					R_part += 1
			elif R_part == len(R_sum)-1:
				a = End - R_sum[R_part-1]
				b = End - R_sum[R_part-2]
				
				if b <= a:
					R_part -= 1
			else:
				a = End - R_sum[R_part-1]
				b = End - R_sum[R_part-2]
				c = End - R_sum[R_part]
				
				if b <= a and b <= c:
					R_part += 1
				elif c <= a and c <= b:
					R_part -= 1
		R_part += i
		
		PP = a_sum[L_part-1]
		QQ = a_sum[i-1] - a_sum[L_part-1]
		RR = a_sum[R_part-1] - a_sum[i-1]
		SS = a_sum[-1] - a_sum[R_part-1]
		
		tmp = max(PP,QQ,RR,SS) - min(PP,QQ,RR,SS)
		if ans == -1 or ans > tmp:
			ans = tmp
	
	print(ans)
	
	
if __name__ == "__main__":
	main()


from itertools import accumulate, islice
from bisect import bisect_left
 
n = int(input())
xs = [int(x) for x in input().split()]
 
ys = list(accumulate(xs))
zs, total = ys[:-1], ys[-1]
 
res = max(xs) - min(xs)
for i, z in islice(enumerate(zs), 1, n-1):
    j = bisect_left(zs, z//2)
    splits = ((zs[j+k], z - zs[j+k]) for k in (-1, 0, 1) if 0 <= j+k <= i)
    a, b = min(splits, key=lambda s:abs(s[0]-s[1]))
 
    j = bisect_left(zs, (total - z)//2 + z)
    splits = ((zs[j+k] - z, total - zs[j+k]) for k in (-1, 0, 1) if i <= j+k <= n-2)
    c, d = min(splits, key=lambda s:abs(s[0]-s[1]))
 
    minn, _, _, maxx = sorted((a,b,c,d))
    if maxx - minn < res:
        res = maxx - minn
 
print(res)

Verdicts: Wrong Answer

Accepted