题意

要求子集和的中位数。

思路

手玩几组样例可以发现一个很重要的性质。 定义数组的和为$S$，假设存在某种子集和为 $x$，必然存在 $S - x$，当然这是算空集的情况下，不过我们还是可以注意到这种情况总是会对称，所以可以发现只需要找到第一个大于等于$\lceil \frac {S}{2} \rceil$的子集和即可。

那就变成了$01背包$，但是满分数据很大.

我们可以使用$bitset$优化，$bitset<N>$可以看作一个长度为N的bool数组，只是它支持整体左右移，和位运算，并且移动位运算复杂度是$\frac{N}{w}$

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
bitset<2000 * 2000 + 1> bs;
int main()
{
    ll N;
    cin >> N;
    bs[0] = 1;
    ll S = 0;
    for (int i = 0; i < N; i++) {
       int x;
       cin >> x;
       bs = bs << x | bs;
       S += x; 
    }
    cout << bs._Find_next((S + 1) / 2 - 1);

    return 0;
}