Submission #2873084

---

Source Code Expand

using System;
using System.Collections.Generic;
using System.Linq;
using static System.Console;

namespace AtCorder
{
	public class Program
	{
		public static void Main()
		{
			int n = int.Parse(ReadLine());
			var list = ReadLine().Split().Select(x => int.Parse(x))
				.ToList();

			// 累積和を使う
			var sum = new List<double>();
			sum.Add(list[0]);
			for (int i = 1; i < n; i++)
			{
				sum.Add(sum[i - 1] + list[i]);
			}

			var ans = double.MaxValue;
			var list2 = new double[4];

			// 中央の区切りは全探索
			for (int i = 1; i < n - 2; i++)
			{
				// 左区間の区切り
				int left = 0;
				while (left < i &&
					 // sum[left + 1] - (sum[i] - sum[left + 1]) = 2 * sum[left + 1] - sum[i]
					 // sum[left] - (sum[i] - sum[left]) = sum[left] - sum[i] + sum[left] = 2 * sum[left] - sum[i]
					 // 境界を求める。一つ先が減っているなら、次へ移動する。
					 Math.Abs(2 * sum[left + 1] - sum[i]) < Math.Abs(2 * sum[left] - sum[i]))
				{
					left++;
				}

				// 右区間の区切り
				int right = i + 1;
				while (right < n &&
					// (sum[right] - sum[i]) - (sum[n-1] - sum[right]) = sum[right] - sum[i] - sum[n-1] - sum[right] = 2 * sum[right] - sum[i] - sum[n-1]
					Math.Abs(2 * sum[right + 1] - sum[i] - sum[n - 1]) < Math.Abs(2 * sum[right] - sum[i] - sum[n - 1]))
				{
					right++;
				}

				list2[0] = sum[left];
				list2[1] = sum[i] - sum[left];
				list2[2] = sum[right] - sum[i];
				list2[3] = sum[n - 1] - sum[right];
				ans = Math.Min(ans, list2.Max() - list2.Min());
			}

			WriteLine(ans);
		}
	}
}

Submission Info

Judge Result