事情是这样的，我不会T2，然后猜测答案是带有一些条件限制的最大化若干元素的和，然后乱搞+调参花了半天才过。其实数据很强，只是我的乱搞过于离谱。

如果有人给出了hack希望能加到数据中

#include<bits/stdc++.h>
using namespace std;
int a[2006],dp[2006][40006],b[2006],t[4006];
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	//int t;
	//cin>>t;
	//while(t--)
	//{for(int i=1;i<=20;i++) for(int j=5000-20;j<=5000+20;j++) dp[i][j]=0;
	int n;
	cin>>n;
	int js=0;
	for(int i=1;i<=n;i++) cin>>a[i];
	if(n==1)
	{
		cout<<a[1];
		return 0;
	}
	int minn=1e9,maxn=-1e9;
	for(int i=1;i<=n;i++) minn=min(minn,a[i]),maxn=max(maxn,a[i]);
	if(minn>=0)
	{
		cout<<maxn;
		//continue;
		return 0;
	}
	if(maxn<=0)
	{
		int da=-1e9;
		for(int i=1;i<=n;i++) if(a[i]) da=max(da,a[i]);
		if(da==-1e9) cout<<'0';
		else cout<<da;
		//continue;
		return 0;
	}
	for(int i=1;i<=n;i++) t[a[i]+2000]++;
	n=0;
	for(int i=0;i<=4000;i++)
		for(int j=1;j<=min(t[i],500);j++)
		{
			a[++n]=i-2000;
		}
	for(int i=1;i<=n-1;i++) swap(a[i],a[rand()%(n-i)+1+i]);
	int jl;
	if(maxn>0)
	{
		for(int i=1;i<=n;i++)
		{
			if(a[i]==maxn)
			{
				jl=i;
				break;
			}
		}
		swap(a[jl],a[n]);
		n--;
	}
	dp[0][10000]=-1;
	for(int i=1;i<=n;i++)
	{
		for(int j=0;j<=20000;j++)
		{
			dp[i][j]=dp[i-1][j];
			if(0<=j-a[i]&&j-a[i]<=20000)
			{
				if(j==10000)
				{
					if(dp[i-1][j-a[i]]&&a[i]) dp[i][j]=1;
				}
				else dp[i][j]=(dp[i][j]||dp[i-1][j-a[i]]);
			}
		}
	}
	for(int i=20000;i>=0;i--)
	{
		if(maxn>0&&i>10000) continue;
		if(dp[n][i]==1)
		{
			if(maxn>0) cout<<i-10000+a[n+1];
			else cout<<i-10000;
			break;
		}
	}
	//}
	return 0;
}
/*
10
2000 2000 2000 2000 -1999 -1999 -1999 -1999 -10 2000
20
2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000
*/