这道题在我做的前一天被wjw大佬压中了，当时随便脑洞了一个做法

于是在比赛还剩3分钟的时候我把它写了一下就切了

考虑一个集合S，f(S)=ΣSi 显然我们将所有的f排序之后有一个性质rank[f(S)]+rank[f(~S)]=2^N

那么显然，中位数就是将全集划分为两个尽可能平均的集合的较大一部分

我们考虑dp,f[i]=max(f[i-v[j]]+v[j]) ，答案即为f[S/2]

这样显然会超时，我们要用bitset来优化，方程为f[i]=f[i]|f[i<<v[j]]，复杂度O(n^3/128)

 

#pragma GCC optimize("O3")#pragma G++ optimize("O3")#include
    
      #include
     
      #include
      
       #include
       
        using namespace std;int n,v[2010],S,T;bitset<2000*1000> f;int main(){	freopen("will.in","r",stdin);	freopen("will.out","w",stdout);	scanf("%d",&n);	for(int i=1;i<=n;++i) scanf("%d",v+i),S+=v[i];	T=S; S>>=1; f[0]=1;	for(int i=1;i<=n;++i) f|=f<