Language: C++

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <vector>
#include <string>
#include <iostream>
#include <algorithm>
#include <map>
#include <iterator>
#include <functional>
#include <set>
#include <stack>
#include <queue>
#include <deque>
#include <fstream>
#include <iomanip>
#include <numeric>
#include <cmath>
#include <list>
#include <sstream>
#include <complex>
#include <stdio.h>
#include <unordered_set>
using namespace std;
#pragma GCC optimize("O3")
#pragma GCC target("sse4")

typedef double LD;
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LD, LD> PDD;
typedef pair<LL, LL> PLL;
typedef vector<int> VI;
typedef vector<LL> VLL;
typedef vector<char> VCH;
typedef vector<LD> VLD;
typedef vector<string> VS;
typedef vector<VS> VSS;
typedef vector<VI> VVI;
typedef vector<VLL> VVLL;
typedef vector<VCH> VVCH;
typedef vector<PII> VPII;
typedef vector<PLL> VPLL;
typedef vector<PDD> VPDD;
#define MP make_pair
#define PB push_back
#define X first
#define Y second
#define next fake_next
#define prev fake_prev
#define left fake_left
#define right fake_right

#define FOR(i,a,b) for(int i = (a); i < (b); ++i)
#define RFOR(i,b,a) for(int i = (b) - 1; i >= (a); --i)
#define REP(i, t) FOR(i,0,t)
#define ALL(a) a.begin(), a.end()
#define SZ(a) (int)((a).size())

const LD PI = acos(-1.0);
const LL mod = 1000000007;
const LL INF = 1e9;
const LL LINF = 1e18;
const LL MAXN = 4e6 + 1;
const LL MAXS = 100 + 1;
const LL MAXT = 100 + 1;


void solve(int a, int b, int c, int d)
{
	string res;
	if (a == b)
	{
		res.assign(a + b, 'A');
		for (int i = 1; i < SZ(res); i += 2)
			res[i] = 'B';

		FOR(i, c, d + 1)
			cout << res[i];

		return;
	}

	if (a > b)
	{
		res.assign(a + b, 'A');
		int k = (a + b) / (b + 1);

		if (a == b + 1)
		{
			for (int i = 1; i < SZ(res); i += 2)
				res[i] = 'B';
		}
		else
		{
			for (int i = k; i < SZ(res); i += (k + 1))
				res[i] = 'B';
		}
	

		FOR(i, c, d + 1)
			cout << res[i];

		return;
	}
	
	if (a == 1)
	{
		res.assign(a + b, 'B');
		res[b / 2] = 'A';
		FOR(i, c, d + 1)
			cout << res[i];
		return;
	}
		
	res.assign(a + b, 'B');
	string res2(a + b, 'B');

	if (b == a + 1)
	{
		for (int i = 1; i < SZ(res); i += 2)
			res[i] = 'A';
	}
	else
	{
		int k = (b + a - 1) / a;
		for (int i = 0; i < SZ(res); i += (k + 1))
			res2[i] = 'A';

		int k2 = (b + a) / (a + 1);
		int r = b - k2 * a;
		if (r > 0)
		{
			for (int i = r; i < SZ(res); i += (k + 1))
				res[i] = 'A';

			if (k <= k2)
			{
				if (k < k2)
					res = res2;
				else
				{
					bool ok = 0;
					FOR(i, 0, SZ(res))
						if (res[i] > res2[i])
						{
							ok = 1;
							break;
						}
					if (ok)
						res = res2;
				}
			}
		}
		else
			res = res2;
	}

	FOR(i, c, d + 1)
		cout << res[i];
}

VCH DP;
VCH prev;

int main()
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	//freopen("In.txt", "r", stdin);
	//freopen("In.txt", "w", stdout);

	clock_t st = clock();

	LL n;
	cin >> n;
	VLL a(n);
	FOR(i, 0, n)
		cin >> a[i];

	int s = 0;
	FOR(i, 0, n)
		s += a[i];

	sort(ALL(a));
	if (s <= 2 * a[n - 1])
	{
		cout << 2 * a[n - 1];
		return 0;
	}

	srand(time(NULL) ^ mod);
	int ans = s;
	int curr = 0;
	
	FOR(i, 0, n)
	{
		curr += a[i];
		curr += a[n - 1 - i];
		if (curr * 2 >= s)
		{
			ans = min(ans, curr);
			break;
		}
	}
	
	while ((clock() - st) < 1.9 * CLOCKS_PER_SEC)
	{
		curr = 0;
		FOR(i, 0, n)
		{
			curr += a[i];
			if (curr * 2 >= s)
			{
				ans = min(ans, curr);
				ans = min(ans, s - (curr - a[i]));
				break;
			}
		}

		random_shuffle(ALL(a));
	}

	cout << ans;
	/*int q;
	int a, b, c, d;
	cin >> q;
	REP(Q, q)
	{
		cin >> a >> b >> c >> d;
		solve(a, b, c - 1, d - 1);
		cout<< endl;
	}*/

	return 0;
}

Compiler output:
a.cc: In function 'int main()':
a.cc:214:42: error: no matching function for call to 'min(int&, __gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type)'
  214 |                                 ans = min(ans, s - (curr - a[i]));
      |                                       ~~~^~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/14/vector:62,
                 from a.cc:3:
/usr/include/c++/14/bits/stl_algobase.h:233:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::min(const _Tp&, const _Tp&)'
  233 |     min(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/14/bits/stl_algobase.h:233:5: note:   template argument deduction/substitution failed:
a.cc:214:42: note:   deduced conflicting types for parameter 'const _Tp' ('int' and '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'})
  214 |                                 ans = min(ans, s - (curr - a[i]));
      |                                       ~~~^~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_algobase.h:281:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::min(const _Tp&, const _Tp&, _Compare)'
  281 |     min(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/14/bits/stl_algobase.h:281:5: note:   candidate expects 3 arguments, 2 provided
In file included from /usr/include/c++/14/algorithm:61,
                 from a.cc:6:
/usr/include/c++/14/bits/stl_algo.h:5686:5: note: candidate: 'template<class _Tp> constexpr _Tp std::min(initializer_list<_Tp>)'
 5686 |     min(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/14/bits/stl_algo.h:5686:5: note:   candidate expects 1 argument, 2 provided
/usr/include/c++/14/bits/stl_algo.h:5696:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::min(initializer_list<_Tp>, _Compare)'
 5696 |     min(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/14/bits/stl_algo.h:5696:5: note:   template argument deduction/substitution failed:
a.cc:214:42: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
  214 |                                 ans = min(ans, s - (curr - a[i]));
      |                                       ~~~^~~~~~~~~~~~~~~~~~~~~~~~
a.cc:219:31: warning: 'void std::random_shuffle(_RAIter, _RAIter) [with _RAIter = __gnu_cxx::__normal_iterator<long long int*, vector<long long int> >]' is deprecated: use 'std::shuffle' instead [-Wdeprecated-declarations]
  219 |                 random_shuffle(ALL(a));
      |                 ~~~~~~~~~~~~~~^~~~~~~~
/usr/include/c++/14/bits/stl_algo.h:4492:5: note: declared here
 4492 |     random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last)
      |     ^~~~~~~~~~~~~~