makrusak

1115 timus

Nov 18th, 2012
134
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.68 KB | None | 0 0
  1. #include <cstdio>
  2. #include <iostream>
  3. #include <algorithm>
  4. #include <vector>
  5. #include <string>
  6. #include <string.h>
  7. #include <queue>
  8. #include <map>
  9. #include <set>
  10. #include <cmath>
  11. #include <sstream>
  12. #include <stack>
  13. #include <cassert>
  14.  
  15. #define pb push_back
  16. #define mp make_pair
  17. #define PI 3.1415926535897932384626433832795
  18. #define sqr(x) (x)*(x)
  19. #define forn(i, n) for(int i = 0; i < n; ++i)
  20. #define ALL(x) x.begin(), x.end()
  21. #define F first
  22. #define S second
  23. #define m0(x) memset(x,0,sizeof(x))
  24. #define m1(x) memset(x,-1,sizeof(x))
  25. #define CC(x) cout << (x) << "\n"
  26. #define pw(x) (1ull<<(x))
  27.  
  28. using namespace std;
  29. typedef long long ll;
  30. typedef unsigned long long ull;
  31. typedef long double ld;
  32. typedef pair<int,int> pii;
  33. const int INF = 2147483647;
  34. const ll LLINF = 9223372036854775807LL;
  35.  
  36. int n,m;
  37. int a[110];
  38. int p[110];
  39. int b[11];
  40. int val;
  41.  
  42. void dfs(int k) {
  43.   if (k==m) {
  44.     vector<int> z[11];
  45.     for (int i=0;i<n;i++) {
  46.       if (p[i]==-1) continue;
  47.       z[p[i]].pb(i);
  48.     }
  49.     for (int i=0;i<m;i++) {
  50.       printf("%d\n", z[i].size());
  51.       for (int j=0;j<z[i].size();j++) printf("%d ", a[z[i][j]]);
  52.       printf("\n");
  53.     }
  54.     exit(0);
  55.   }
  56.   if (b[k]==0) {
  57.     dfs(k+1);
  58.     return;
  59.   }
  60.   for (int i=0;i<n;i++) {
  61.     if (p[i]!=-1) continue;
  62.     if (a[i]<=b[k]) {
  63.       b[k]-=a[i];
  64.       p[i]=k;
  65.       dfs(k);
  66.       p[i]=-1;
  67.       b[k]+=a[i];
  68.     }
  69.   }
  70. }
  71.  
  72. int main() {
  73.   //freopen("input.txt", "r", stdin);
  74.   //freopen("output.txt", "w", stdout);
  75.   scanf("%d %d", &n, &m);
  76.   m1(p);
  77.   for (int i=0;i<n;i++) scanf("%d", &a[i]);
  78.   sort(a, a+n);
  79.   reverse(a, a+n);
  80.   for (int i=0;i<m;i++) scanf("%d", &b[i]);
  81.   dfs(0);
  82.   return 0;
  83. }
Advertisement
Add Comment
Please, Sign In to add comment