[口胡记录] AGC020C Median Sum

（题目传送门）

一开始口胡结论，发现假了……

把所有的子集和放到数轴上，惊奇地发现它们关于 \(\dfrac{sum}{2}\) 对称，于是做一遍存在性背包，从 \(\dfrac{sum}{2}\) 开始找第一个存在的子集和就好了

因为 \(n,a_i\leq 2000\)，需要 \(\rm bitset\) 优化

#include<bits/stdc++.h>
using namespace std;

const int N=2010;

int n,a[N],sum;
bitset <N*N> f;

int main()
{
	scanf("%d",&n);
	for(int i=1; i<=n; i++)
		scanf("%d",&a[i]),sum+=a[i];
	
	f[0]=1;
	for(int i=1; i<=n; i++)
		f|=f<<a[i];
	
	for(int i=ceil(1.0*sum/2); i<=sum; i++)
	{
		if(f[i])
		{
			printf("%d",i);
			break;
		}
	}

	return 0;
}