[AGC020C] Median Sum

题面

给定由 $n$ 个正整数 $a _ {1, 2, \cdots, n}$ 组成的可重集合，请求出它的非空子集的和的中位数。

$1\ \leq\ n\ \leq\ 2000, 1\ \leq\ A_i\ \leq\ 2000$

题解

发现重要性质，非空子集的和在值域上是对称的。bitset 背包即可。

代码

const int N = 2001, M = N * N;

inline ll Read() {
	ll x = 0, f = 1;
	char c = getchar();
	while (c != '-' && (c < '0' || c > '9')) c = getchar();
	if (c == '-') f = -f, c = getchar();
	while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0', c = getchar();
	return x * f;
}

namespace Main {
	int n, sum;
	bitset <M> f;
	int main () {
		n = Read();
		f[0] = 1;
		for (int i = 1; i <= n; i++) {
			int x = Read();
			f |= f << x;
			sum += x;
		}
		for (int i = (sum + 1) / 2; i <= sum; i++)
			if (f[i]) { printf ("%d\n", i); break;}
		return 0;
	}
}

int main () {
	string str = "";
//	freopen((str + ".in").c_str(), "r", stdin);
//	freopen((str + ".out").c_str(), "w", stdout);
	Main::main();
	return 0;
}