Language: C++

#include <bits/stdc++.h>
using namespace std;

int a[500100];
long long add[500100];
int n;
int sp1, sp2, sp3;

long long direct( int d0, int d1, int d2 )
{
	/*
	cout << "(" << d0 << ", " << d1 << ", " << d2 << ")" << endl;
	cout << " sp1=" << sp1  << endl;
	cout << " sp2=" << sp2  << endl;
	cout << " sp3=" << sp3  << endl;
	*/
	int sp1_d = sp1 + ( (d0==0) ? 0:(d0==1) ? -1:1 );
	int sp2_d = sp2 + ( (d1==0) ? 0:(d1==1) ? -1:1 );
	int sp3_d = sp3 + ( (d2==0) ? 0:(d2==1) ? -1:1 );
	// 0 <= sp1 < n-2 , 2 <= sp3 < n , sp1 < sp2 < sp3
	/*
	cout << " sp1_d=" << sp1_d  << endl;
	cout << " sp2_d=" << sp2_d  << endl;
	cout << " sp3_d=" << sp3_d  << endl;
	*/
	if( sp1_d < 0 ) sp1_d = 0;
	if( n-2 <= sp1_d ) sp1_d = n-2;
	if( sp2_d <= sp1_d ) sp2_d = sp1_d+1;
	if( sp3_d <= sp2_d ) sp2_d = sp3_d-1;
	if( sp3_d < 2 ) sp3_d = 2;
	if( n <= sp3_d ) sp3_d = n-1;

/*
	cout << " sp1_d=" << sp1_d  << endl;
	cout << " sp2_d=" << sp2_d  << endl;
	cout << " sp3_d=" << sp3_d  << endl;
*/

	long long pqrs[4];
	pqrs[0] = add[sp1_d+1];
	pqrs[1] = add[sp2_d+1]- add[sp1_d+1];
	pqrs[2] = add[sp3_d+1]- add[sp2_d+1];
	pqrs[3] = add[n]- add[sp3_d+1];
/*
	cout << "pqrs[0]" << pqrs[0] << endl;
	cout << "pqrs[1]" << pqrs[1] << endl;
	cout << "pqrs[2]" << pqrs[2] << endl;
	cout << "pqrs[3]" << pqrs[3] << endl;
*/
	sort( pqrs, pqrs+4 );
	long long min = (pqrs[3]-pqrs[0]);
//	cout << "min=" << min << endl;
	
	while(1)
	{
		sp1_d = sp1 + ( (d0==0) ? 0:(d0==1) ? -1:1 );
		sp2_d = sp2 + ( (d1==0) ? 0:(d1==1) ? -1:1 );
		sp3_d = sp3 + ( (d2==0) ? 0:(d2==1) ? -1:1 );
		if( sp1_d < 0 ) sp1_d = 0;
		if( n-2 <= sp1_d ) sp1_d = n-2;
		if( sp2_d <= sp1_d ) sp2_d = sp1_d+1;
		if( sp3_d <= sp2_d ) sp2_d = sp3_d-1;
		if( sp3_d < 2 ) sp3_d = 2;
		if( n <= sp3_d ) sp3_d = n-1;
		
		pqrs[0] = add[sp1_d+1];
		pqrs[1] = add[sp2_d+1]- add[sp1_d+1];
		pqrs[2] = add[sp3_d+1]- add[sp2_d+1];
		pqrs[3] = add[n]- add[sp3_d+1];
		sort( pqrs, pqrs+4 );
		long long tmp = (pqrs[3]-pqrs[0]);
		if( tmp < min ) {
			min = tmp;
			continue;
		}
		break;
	}
	return min;
}
int main()
{
	cin >> n;
	for( int i = 0; i < n; i++ ) {
		cin >> a[i];
		add[i+1] = add[i]+a[i];
	}
	// sp# ... 最後に含む要素で表現する
	// 0 <= sp1 < n-2 , 2 <= sp3 < n , sp1 < sp2 < sp3
	
	// 総当りだと n^3 のアルゴリズムなので駄目
	// sp1, sp2 が固定された時、sp3 はどうあるべきか？
	// sp2 からの累積加算SにおけるS/2に最も近い点を sp3 とする
	// じゃあ、累積加算S の S/4, 2S/4, 3S/4 に近い点が最大・最小の差を小さくするのでは？
	//
	// →最適解ではない
	
	// cout << "S=" << add[n] << " d:" << add[n+1] << endl;
	long long S = add[n];
//	cout << "S/4=" << S/4  << endl;
	for( sp1 = 0; sp1 < n-3; sp1++ ) {
		if( abs(add[sp1+1] - S/4) < abs(add[sp1+2] - S/4) ) {
			break;
		}
	}
	for( sp2 = sp1+1; sp2 < n-2; sp2++ ) {
//		cout << "sp2=" << sp2 << endl;
//		cout << (add[sp2+1]- S/2) << ", " << (add[sp2+2]- S/2) << endl;
		if( abs(add[sp2+1] - S/2) < abs(add[sp2+2] - S/2) ) {
			break;
		}
	}
	for( sp3 = sp2+1; sp3 < n-1; sp3++ ) {
		if( abs(add[sp3+1] - 3*S/4) < abs(add[sp3+2] - 3*S/4) ) {
			break;
		}
	}
	/*
	cout << "sp1=" << sp1 << " P=" << add[sp1+1]  << endl;
	cout << "sp2=" << sp2 << " Q=" << add[sp2+1]- add[sp1+1]  << endl;
	cout << "sp3=" << sp3 << " R=" << add[sp3+1]- add[sp2+1]  << endl;
	cout << " S=" << add[n]- add[sp3+1]  << endl;
	*/
	// p1 を止、p2 を止、p3を左　よくなるか？
	// p1 を止、p2 を止、p3を右　よくなるか？
	// p1 を止、p2 を左、p3を止　よくなるか？
	// p1 を止、p2 を左、p3を右　よくなるか？
	// p1 を止、p2 を右、p3を止　よくなるか？
	// p1 を止、p2 を左、p3を左　よくなるか？
	// ここから 27通りの方向に動かしてそれぞれの最適解を探す
	long long min = direct( 0, 0, 0 );
	for( int d0 = 0; d0 < 3; d0++ ) {
		for( int d1 = 0; d1 < 3; d1++ ) {
			for( int d2 = 0; d2 < 3; d2++ ) {
				long long tmp = direct( d0, d1, d2 );
				if( tmp < min  ) {
					min = tmp;
				}
			}
		}
	}
	cout << min << endl;
}
/*

Compiler output:
a.cc:143:1: error: unterminated comment
  143 | /*
      | ^