bzoj 1334: [Baltic2008]Elect

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<algorithm>
 4 #define N 100005
 5 using namespace std;
 6 int a[N],n,tot,f[N],ans;
 7 bool cmp(int a, int b){return a>b;}
 8 int main()
 9 {
10     scanf("%d",&n);
11     for (int i=1; i<=n; i++) scanf("%d",&a[i]),tot+=a[i];
12     tot/=2; sort(a+1,a+n+1,cmp);
13     f[0]=1;
14     for (int i=1; i<=n; i++)
15         for (int j=tot; j>=0; j--)
16             if (f[j]) f[j+a[i]]=1;
17     for (int i=tot+1; i<=tot*2; i++)
18         if (f[i]) ans=i;
19     printf("%d\n",ans);
20     return 0;
21 }