Advertisement
Guest User

Untitled

a guest
Dec 14th, 2014
218
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.19 KB | None | 0 0
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstdlib>
  4. #include <algorithm>
  5. #include <string.h>
  6. #include <ctime>
  7. #include <iomanip>
  8. #include <vector>
  9. #include <set>
  10. #include <map>
  11. #include <queue>
  12. #include <stack>
  13. #include <cmath>
  14.  
  15. using namespace std;
  16.  
  17. #define max(a,b) ((a) >= (b) ? (a) : (b))
  18. #define endl        '\n'
  19.  
  20. long long A[11];
  21. long long B[11];
  22. int dp[5][1<<9];
  23. int rest[5][1<<9];
  24. int p[5][1<<9];
  25. int n,k;
  26.  
  27. int X[11];
  28. int BIT[11];
  29. int ans = 1000000000;
  30. int ABIT[11];
  31.  
  32. void rec(int idx, int aa) {
  33.     if (aa >= ans) return;
  34.     if (idx != k) {
  35.         for (int i = 0; i < n; i++) {
  36.             X[idx] = i;
  37.             BIT[X[idx]] ^= (1<<idx);
  38.             rec(idx+1, max(aa, dp[X[idx]][BIT[X[idx]]]));
  39.             BIT[X[idx]] ^= (1<<idx);
  40.         }
  41.     } else {
  42.         if (aa < ans) {
  43.             ans = aa;
  44.             for (int i = 0; i < n; i++) {
  45.                 ABIT[i] = BIT[i];
  46.             }
  47.         }
  48.     }
  49. }
  50.  
  51. int main( void ) {
  52. //  freopen("input.txt", "rt", stdin);
  53.     cin.tie( 0 ); cin.sync_with_stdio(false);
  54.     while (cin >> n) {
  55.         cin >> k;
  56.         //memset(dp, 0, sizeof(dp));
  57.         memset(p, 0, sizeof(p));
  58.         memset(rest, 0, sizeof(rest));
  59.         for (int i = 0; i < n; i++) {
  60.             dp[i][0] = 0;
  61.             for (int j = 1; j < (1<<k); j++) {
  62.                 dp[i][j] = 1000000000;
  63.             }
  64.         }
  65.         ans = 1000000000;
  66.         for (int i = 0; i < n; i++) {
  67.             cin >> A[i];
  68.         }
  69.         for (int i = 0; i < k; i++) {
  70.             cin >> B[i];
  71.         }
  72.         for (int bit = 1; bit < (1<<k); bit++) {
  73.             for (int i = 0; i < n; i++) {
  74.                 for (int j = 0; j < k; j++) {
  75.                     if (bit & (1<<j)) {
  76.                         if (B[j] > A[i]) {
  77.                             dp[i][bit] = 1000000000;
  78.                             break;
  79.                         }
  80.                         if (rest[i][bit^(1<<j)] >= B[j]) {
  81.                             if (dp[i][bit] > dp[i][bit^(1<<j)] ||
  82.                                (dp[i][bit] == dp[i][bit^(1<<j)] &&
  83.                                rest[i][bit] < rest[i][bit^(1<<j)]-B[j])) {
  84.                                 rest[i][bit] = rest[i][bit^(1<<j)]-B[j];
  85.                                 dp[i][bit] = dp[i][bit^(1<<j)];
  86.                                 p[i][bit] = bit^(1<<j);
  87.                             }
  88.                         } else {
  89.                             if (dp[i][bit] > dp[i][bit^(1<<j)] + 1 ||
  90.                                (dp[i][bit] == dp[i][bit^(1<<j)] + 1 &&
  91.                                rest[i][bit] < A[i]-B[j])) {
  92.                                 dp[i][bit] = dp[i][bit^(1<<j)] + 1;
  93.                                 rest[i][bit] = A[i]-B[j];
  94.                                 p[i][bit] = bit^(1<<j);
  95.                             }
  96.                         }
  97.                     }
  98.                 }
  99.             }
  100.         }
  101.         rec(0,0);
  102.         if (ans >= 100) {
  103.             cout << "-1" << endl;
  104.             continue;
  105.         }
  106.         vector<int> K[11];
  107.         for (int i = 0; i < n; i++) {
  108.             int bit = ABIT[i];
  109.             while (bit) {
  110.                 int nbit = p[i][bit];
  111.                 bit = bit^nbit;
  112.                 for (int j = 0; j < k; j++) {
  113.                     if ((1<<j) == bit) {
  114.                         K[i].push_back(j);
  115.                         break;
  116.                     }
  117.                 }
  118.                 bit = nbit;
  119.             }
  120.             reverse(K[i].begin(), K[i].end());
  121.         }
  122.         int R[11][11];
  123.         memset(R,255,sizeof(R));
  124.         for (int i = 0; i < n; i++) {
  125.             int rest = 0;
  126.             int cnt = 0;
  127.             for (int j = 0; j < (int)K[i].size(); j++) {
  128.                 int a = K[i][j];
  129.                 if (B[a] > rest) {
  130.                     rest = A[i]-B[a];
  131.                     cnt++;
  132.                 } else {
  133.                     rest -= B[a];
  134.                 }
  135.                 R[cnt][a] = i;
  136.             }
  137.         }
  138.         cout << ans << endl;
  139.         for (int i = 1; i <= ans; i++) {
  140.             int cnt = 0;
  141.             for (int j = 0; j < k; j++) {
  142.                 cnt += (R[i][j] != -1);
  143.             }
  144.             cout << cnt << " ";
  145.             for (int j = 0; j < k; j++) {
  146.                 if (R[i][j] == -1) continue;
  147.                 cout << j+1 << " " << R[i][j]+1 << " ";
  148.             }
  149.             cout << endl;
  150.         }
  151.     }
  152.     return 0;
  153. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement