提出 #23007922

---

ソースコード 拡げる

#include <iostream>
#include <iomanip>
#include <vector>
#include <cmath>
#include <algorithm>
#include <set>
#include <utility>
#include <queue>
#include <map>
#include <assert.h>
#include <stack>
#include <string>
#include <ctime>
#include <chrono>
#include <random>
#define int long long int
using namespace std;

const int INF=1e16;

void solve()
{
	int n;
	cin>>n;
	vector<int> v(n+1);
	for (int j=1; j<=n; j++) cin>>v[j];
	if (n <= 2)
	{
		cout << 0 << '\n';
		return;
	}
	v[0]=-INF;
	
	sort(v.begin(), v.end());
	
	int res=v[n]-v[1];
	
	for (int j=1; j<=n/2; j++) //pref-suff len
	{
		int mx=-INF, mn=+INF;
		for (int i=1; i<=j; i++)
		{
			mx=max(mx, v[i]+v[n-i+1]);
			mn=min(mn, v[i]+v[n-i+1]);
		}
		for (int i=j+1; i<=(n+1)/2; i++)
		{
			mx=max(mx, max(v[i], v[n-i+1]));
			mn=min(mn, min(v[i], v[n-i+1]));
		}
		res=min(res, mx-mn);
	}

	for (int j = 2; j <= n; j += 2)
	{
		int mx = -INF, mn = +INF;
		for (int i = 1; i <= j / 2; i++)
		{
			mx = max(mx, v[i]+v[j-i+1]);
			mn = min(mn, v[i]+v[j-i+1]);
		}
		for (int i = j + 1; i <= n; i++)
		{
			mx = max(mx, v[i]);
			mn = min(mn, v[i]);
		}
		res = min(res, mx - mn);
	}
	vector<int> d(n + 1);
	for (int j = 1; j <= n; j++) d[j] = v[n - j + 1];
	v = d;
	for (int j = 2; j <= n; j += 2)
	{
		int mx = -INF, mn = +INF;
		for (int i = 1; i <= j / 2; i++)
		{
			mx = max(mx, v[i] + v[j - i + 1]);
			mn = min(mn, v[i] + v[j - i + 1]);
		}
		for (int i = j + 1; i <= n; i++)
		{
			mx = max(mx, v[i]);
			mn = min(mn, v[i]);
		}
		res = min(res, mx - mn);
	}
	cout << res << '\n';
	return;
}

signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(NULL); cout.tie(NULL);
	int t;
	//cin >> t;
	t=1;
	while (t--)
	{
		solve();
	}
	return 0;
}

提出情報

ジャッジ結果