Advertisement
Guest User

Untitled

a guest
Oct 26th, 2011
162
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.57 KB | None | 0 0
  1. #include <iostream>
  2. #include <algorithm>
  3. using namespace std;
  4. long long int set1[70000],set2[70000];
  5. long long int a[40],b[40],n,na,nb,ns1,ns2,mini,nummini,Tsum,nset;
  6. long long int getsum(long long int *a,long long int id)
  7. {
  8.     long long int res = 0,i;
  9.     for (i = 0;id != 0;++i,id >>= 1)
  10.         if (id & 1) res += a[i];
  11.     return res;
  12. }
  13. void solution()
  14. {
  15.     long long int dif,val,finder,i,j,lowb,uppb;
  16.     ns1 = (1 << na);
  17.     for (i = 0;i < ns1;++i) set1[i] = getsum(a,i);
  18.     ns2 = (1 << nb);
  19.     for (i = 0;i < ns2;++i) set2[i] = getsum(b,i);
  20.     sort(set2,set2 + ns2);
  21.     mini = -1;
  22.     for (i = 0;i < ns1;++i)
  23.     {
  24.         if (mini != -1) lowb = (Tsum - mini) / 2 - set1[i]; else lowb = 0;
  25.         uppb = Tsum / 2 + 1 - set1[i];
  26.         lowb = lower_bound(set2, set2 + ns2, lowb) - set2;
  27.         uppb = upper_bound(set2, set2 + ns2, uppb) - set2;
  28.         for (j = max(lowb - 1,0LL);j < uppb;++j)
  29.         {
  30.             val = set1[i] + set2[j];
  31.             dif = abs(Tsum - val - val);
  32.             if ((dif == mini) && (nset == val)) ++nummini;
  33.             else if ((dif < mini) || (mini == -1))
  34.             {
  35.                 nset = val;
  36.                 mini = dif;
  37.                 nummini = 1;
  38.             }
  39.         }
  40.     }
  41.     if (mini == 0) nummini = nummini / 2;
  42. }
  43. int main()
  44. {
  45.     int i;
  46.     cin >> n;
  47.     na = n/2;
  48.     nb = n - na;
  49.     Tsum = 0;
  50.     for (i = 0;i < na;++i) {cin >> a[i];Tsum += a[i];}
  51.     for (i = 0;i < nb;++i) {cin >> b[i];Tsum += b[i];}
  52.     solution();
  53.     cout << mini << ' ' << nummini << endl;
  54.     return 0;
  55. }
  56.  
  57.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement