Advertisement
Guest User

Untitled

a guest
May 15th, 2014
218
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.98 KB | None | 0 0
  1. #include <cstdio>
  2. #include <algorithm>
  3. #include <functional>
  4.  
  5. typedef std::pair<char, int> solution_t;
  6. int A[24], C[100];
  7. solution_t T[16777216];
  8.  
  9. int main() {
  10.     int n, m;
  11.     scanf("%d %d", &n, &m );
  12.     for( int i = 0; i < n; i++ )
  13.         scanf("%d", A+i);
  14.     for( int i = 0; i < m; i++ )
  15.         scanf("%d", C+i);
  16.        
  17.     std::sort(C, C+m, std::greater<int>() );
  18.    
  19.     if( m > n )
  20.         m = n;
  21.        
  22.     T[0] = solution_t(1,0);
  23.     for( int S = 1; S < (1<<n); S++ ) {
  24.         T[S] = solution_t(n+1,0);
  25.         for( int i = 0; (1<<i) <= S; i++ ) {
  26.             if( (1<<i) & S ) {
  27.                 int P = S ^ (1<<i);
  28.                 solution_t Q = T[P];
  29.                 if( Q.first == n+1 )
  30.                     continue;
  31.                 Q.second += A[i];
  32.                 if( Q.second > C[Q.first-1] ) {
  33.                     Q.first++;
  34.                     Q.second = A[i];
  35.                     if( Q.second > C[Q.first-1] )
  36.                         Q.first = n+1;
  37.                 }
  38.                 if( Q < T[S] )
  39.                     T[S] = Q;
  40.             }
  41.         }
  42.     }
  43.     solution_t solution = T[(1<<n)-1];
  44.     if( solution.first == n+1 ) {
  45.         puts("NIE");
  46.     } else {
  47.         printf("%d\n", solution.first );
  48.     }
  49.    
  50.     return 0;
  51. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement