思路就是背包 bb为背包数组
mxz为最大数 bb中mxz前面为正后面为负 保证每次正数只能加在负数上
X是试出来的(但一定不影响第一个点)

#include <iostream>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <queue>
#include <cstdio>
#include <map>
#include <vector>
#include <list>
#include <functional>
#include <stack>
#include <unordered_map>
#include <set>
#include <cctype>
#include <cstring>
#include <bitset>
#include <unordered_set>
#define m(a,b) make_pair(a,b)
#define F first
#define S second
#define ll long long
#define ull unsigned long long
#define us unsigned short
#define MAX(a,b) (a>b?a:b)
#define MIN(a,b) (a<b?a:b)
#define XOR(a,b) ((a&&!b)||(!a&&b))
using namespace std;
const int M=1e9,N=2003,X=400000;int YI=1,LING=0;const ll P=998244353;
bool bb[N*N];
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr),cout.tie(nullptr);
	//freopen("in.txt","r",stdin);
	//freopen("out.txt","w",stdout);
	int n,a[N]={},m=0,mxz=0,mxf=-M,zheng=0,fu=0,zh=0,fh=0;
	cin>>n;
	for(int i=0;i<n;i++)
	{
		cin>>a[i];
		if(a[i]>0)
			mxz=MAX(a[i],mxz),zheng++,zh+=a[i];
		else if(a[i]<0)
			mxf=MAX(mxf,a[i]),fu++,fh-=a[i];
	}
	if(fu==0)
	{
		cout<<mxz;
		return 0;
	}
	else if(zheng==0)
	{
		cout<<mxf;
		return 0;
	}
	else if(zheng==1)
	{
		cout<<mxz+mxf;
		return 0;
	}//亿点点特判
	sort(a,a+n);
	m=mxz+min({zh,fh,X});
	for(int i=0;i<n;i++)
	{
		if(a[i]<0)
		{
			for(int j=m;j+a[i]>=mxz;j--)
			{
				if(bb[j+a[i]]&&!bb[j])
					bb[j]=1;
			}
			bb[mxz-a[i]]=1;
		}
		else if(a[i]>0)
		{
			for(int j=0;j<=m-a[i];j++)
			{
				if(bb[j+a[i]]&&!bb[j])
					bb[j]=1;
			}
		}
	}
	for(int i=0;i<=m;i++)
	{
		if(bb[i])
		{
			cout<<mxz-i;
			return 0;
		}
	}
	return 0;
}