sultan

1115

Nov 18th, 2012
119
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.05 KB | None | 0 0
  1. #include <cstdio>
  2. #include <cstdlib>
  3. #include <cstring>
  4. #include <string>
  5. #include <map>
  6. #include <set>
  7. #include <vector>
  8. #include <algorithm>
  9. #include <queue>
  10. #include <bitset>
  11. #include <stack>
  12. #include <iostream>
  13. #include <fstream>
  14. #include <cmath>
  15. #include <ctime>
  16.  
  17. #define sqr(a) ((a)*(a))
  18. #define odd(a) ((a)&1)
  19. #define foru(i,n) for (int i=0;i<(n);i++)
  20. #define ford(i,n) for (int i=(n)-1;i>=0;i--)
  21. #define forab(i,l,r) for (int i=(l);i<=(r);i++)
  22. #define forabd(i,r,l) for (int i=(r);i>=(l);i--)
  23. #define pb push_back
  24. #define F first
  25. #define S second
  26. #define all(x) x.begin(),x.end()
  27. #define sz(__X) (int)__X.size()
  28. #define pii pair<int,int>
  29.  
  30. const double eps=1e-19;
  31. const double PI=acos(-1.0);
  32. const int INF=1000*1000*1000+7;
  33. const int MAXN = 100005;
  34.  
  35. using namespace std;
  36.  
  37. int n,m;
  38. int a[MAXN];
  39. int b[MAXN];
  40. vector<int> ans[15];
  41. vector<int> pr[10000];
  42. bool was[105];
  43.  
  44. void rec(int x)
  45. {
  46.     if ( x == m)
  47.     {
  48.         for (int i=0; i<m; i++)
  49.         {
  50.             printf("%d\n", sz(ans[i]));
  51.             for (int j=0;j<sz(ans[i]); j++)
  52.                 printf("%d ", ans[i][j]);
  53.             printf("\n");
  54.         }
  55.         exit(0);
  56.     }
  57.     int u = b[x];
  58.     for (int j=0; j<sz(pr[u]); j++)
  59.     {
  60.         if ( !was[pr[u][j]] )
  61.         {
  62.             int v = pr[u][j];
  63.             ans[x].push_back(a[v]);
  64.             was[v]=true;
  65.             b[x] -= a[v];
  66.             if ( b[x] == 0)
  67.                 rec(x+1);
  68.                 else rec(x);
  69.             b[x]+=a[v];
  70.             ans[x].pop_back();
  71.             was[v]=false;
  72.         }
  73.     }
  74. }
  75.  
  76. int main()
  77. {
  78.     //freopen("input.txt", "r", stdin);
  79.     //freopen("output.txt", "w", stdout);
  80.     scanf("%d %d", &n, &m);
  81.     pr[0].push_back(-1);
  82.     for (int i=0; i<n; i++)
  83.     {
  84.         scanf("%d", &a[i]);
  85.     }
  86.     srand(time(NULL));
  87.     sort(a, a+n);
  88.     for (int i=n; i>=0; i--)
  89.     {
  90.         for (int j=9900; j>=0; j--)
  91.         {
  92.             if ( !pr[j].empty() )
  93.                 pr[j+a[i]].push_back(i);
  94.         }
  95.     }
  96.     for (int i=0; i<m; i++)
  97.         scanf("%d", &b[i]);
  98.     rec(0);
  99.     return 0;
  100. }
Advertisement
Add Comment
Please, Sign In to add comment