agc 020C - Median Sum[bitset]

Problem Statement

You are given $N$ integers $A_1$, $A_2$, …, $A_N$.

Consider the sums of all non-empty subsequences of $A$. There are $2^N−1$ such sums, an odd number.

Let the list of these sums in non-decreasing order be $S_1$, $S2$, …, $S{2^N}−1$.

Find the median of this list, $2^N−1$.

Constraints

$1≤N≤2000$
$1≤A_i≤2000$
All input values are integers.

Input

Input is given from Standard Input in the following format:
N
A1 A2 … AN

Output

Print the median of the sorted list of the sums of all non-empty subsequences of A.

Sample Input 1

3
1 2 1

Sample Output 1

2
In this case, S=(1,1,2,2,3,3,4). Its median is S4=2.

Sample Input 2

1
58

Sample Output 2

58
In this case, S=(58).

Solution

考虑对称性,除开全选,都有一种与之对应的情况。

考虑相等的情况,因为对称性,所以并不影响结果。

所以是找一些数的和,接近所有数的和/2。

然后就可以暴力了,用bitset搞,可以除一个32,然后就可以了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int qmax(int &x,int y) {if (x<y) x=y;}
int qmin(int &x,int y) {if (x>y) x=y;}
int read()
{
char s;
int k=0,base=1;
while((s=getchar())!='-'&&s!=EOF&&!(isdigit(s)));
if(s==EOF)exit(0);if(s=='-')base=-1,s=getchar();
while(isdigit(s)){k=k*10+(s^'0');s=getchar();}
return k*base;
}
void write(int x)
{
if(x<0){putchar('-');write(-x);}
else{if(x/10)write(x/10);putchar(x%10+'0');}
}
int n,x;
int a[5000000],p;
bitset<4111111> k;
int main()
{
n=read();
k[0]=1;
for (int i=1;i<=n;i++)
{
x=read();
k|=k<<x;
}
for (int i=1;i<=4000000;i++)
{
if (k[i]) a[++p]=i;
}
cout<<a[(p+1)/2];
}