我在打比赛的时候搞了个乱搞做法，首先肯定是要特判所有数都>0和都<0的情况，然后把最大值拿出来，剩下的数跑0-1背包，背包的值域要开到n|a[i]|，就是2000*2000，必须得用bitset优化才能过。

不过本蒟蒻的乱搞做法是：把背包的值域只开到64000，然后random_shuffle随机排一下序列再跑背包，重复一共5次取最大值，然后比赛的时候就全AC了，不知道这个做法能不能被hack掉

#include<bits/stdc++.h>
using namespace std;
const int mn=2000;

int n,a[mn+3];
bool dp[128003];

int main() {
    //cout<<sizeof(dp)/1048576;
    cin>>n;
    for(int i=1;i<=n;i++) scanf("%d",a+i);
    sort(a+1,a+n+1);
    if(a[1]>=0||a[n]<=0) {
        //全同号或者是0
        for(int i=n;i>=1;i--) {
            if(a[i]!=0) {
                cout<<a[i];
                return 0;
            }
        }
        cout<<0;
        return 0;
    }
    //for(int i=1;i<=n;i++) cout<<a[i]<<" ";

    srand(time(0));
    int tans=-2e9;
    for(int z=1;z<=5;z++) {
        random_shuffle(a+1,a+n-1+1);
        const int S=64000;
        memset(dp,false,sizeof(dp));
        dp[0+S]=true;
        for(int i=1;i<=n-1;i++) {
            if(a[i]!=0&&dp[S-a[i]]) {
                //能加减得到0
                tans=0;
                goto OK;
            }
            if(a[i]>0) 
                for(int j=2*S-a[i];j>=0;j--) 
                    dp[j+a[i]]|=dp[j];
            if(a[i]<0) 
                for(int j=0-a[i];j<=2*S;j++) 
                    dp[j+a[i]]|=dp[j];
        }
        int ans=0;
        for(int j=S-1;j>=0;j--) 
            if(dp[j]) {
                ans=j-S;
                break;
            }
        tans=max(ans,tans);
    }
    OK:
    cout<<tans+a[n];
    return 0;
}