Advertisement
LinKin

ytytu

Dec 14th, 2014
477
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.10 KB | None | 0 0
  1. #pragma comment(linker, "/STACK:16777216")
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4.  
  5. #define CLR(a) memset(a,0,sizeof(a))
  6. #define SET(a) memset(a,-1,sizeof(a))
  7. #define pb push_back
  8. #define SZ(a) ((long)a.size())
  9. #define ALL(a) a.begin(),a.end()
  10. #define FOREACH(i, c) for( __typeof( (c).begin() ) i = (c).begin(); i != (c).end(); ++i )
  11. #define AREA2(x1,y1,x2,y2,x3,y3) ( x1*(y2-y3) + x2*(y3-y1) + x3*(y1-y2) )
  12. #define SQR(x) ((x)*(x))
  13. #define STR string
  14. #define IT iterator
  15. #define ff first
  16. #define ss second
  17. #define MP make_pair
  18. #define EPS 1e-9
  19. #define INF 1000000007
  20.  
  21. #define chk(a,k) ((bool)(a&(1<<(k))))
  22. #define set0(a,k) (a&(~(1<<(k))))
  23. #define set1(a,k) (a|(1<<(k)))
  24.  
  25. typedef long long Long;
  26. typedef vector<long> Vl;
  27. typedef vector<Long> VL;
  28. typedef pair<long,long> Pll;
  29. typedef pair<Long,Long> PLL;
  30.  
  31. inline long FastMax(long x, long y) { return (((y-x)>>(32-1))&(x^y))^y; }
  32. inline long FastMin(long x, long y) { return (((y-x)>>(32-1))&(x^y))^x; }
  33.  
  34. long IR[] = { 0,-1,0,1,-1,-1,1,1 };
  35. long IC[] = { 1,0,-1,0,1,-1,-1,1 };
  36.  
  37. #define MAX 10
  38.  
  39. long N,K;
  40. long cap[MAX+7];
  41. long wei[MAX+7];
  42. long wS[1<<MAX];
  43. bool vi[1<<MAX][MAX+7];
  44. long sol[1<<MAX][MAX+7];
  45. long st[1<<MAX][MAX+7];
  46.  
  47. long Find( long b, long t ){
  48.     if( !b ) return 0;
  49.     if( vi[b][t] ) return sol[b][t];
  50.     vi[b][t] = true;
  51.     sol[b][t] = INF;
  52.     long subs = b;
  53.     while( 1 ){
  54.         if( wS[subs] <= cap[t] ){
  55.             long tmp = Find( b & ~subs, (t+1)%N );
  56.             if( tmp < sol[b][t] ){
  57.                 sol[b][t] = tmp;
  58.                 st[b][t] = subs;
  59.             }
  60.         }
  61.         if( !subs ) break;
  62.         subs = (subs-1) & b;
  63.     }
  64.     return sol[b][t] = sol[b][t] + (t==0);
  65. }
  66.  
  67. void printSol( long b, long t, vector<Pll> &del ){
  68.     long i;//printf("%ld %ld\n",b,t );
  69.     if( (t==0 or !b) and del.size() ){
  70.         printf("%ld",del.size() );
  71.         for( i=0;i<del.size();i++ ){
  72.             printf(" %ld %ld",del[i].ff, del[i].ss );
  73.         }
  74.         printf("\n");
  75.         del.clear();
  76.     }
  77.     if( !b ) return;
  78.     for( i=0;i<K;i++ ){
  79.         if( st[b][t] & (1<<i ) ){
  80.             del.pb( MP( (i+1),( t+1 ) ) );
  81.         }
  82.     }
  83.     printSol( b & ~st[b][t], (t+1)%N, del );
  84. }
  85.  
  86. int main( void )
  87. {
  88.     long i,j,Icase,k=0;
  89.  
  90.     //freopen("text1.txt","r",stdin );
  91.     freopen("dhl.in","r",stdin );
  92.     freopen("dhl.out","w",stdout );
  93.  
  94.     while( cin>>N>>K ){
  95.         long mC = 0;
  96.         for( i=0;i<N;i++ ){
  97.             cin>>cap[i];
  98.             mC = max( mC, cap[i] );
  99.         }
  100.         long mW = 0;
  101.         for( i=0;i<K;i++ ){
  102.             cin>>wei[i];
  103.             mW = max( mW, wei[i] );
  104.         }
  105.         if( mC < mW ){
  106.             printf("-1\n");
  107.             continue;
  108.         }
  109.         for( i=0;i<(1<<K);i++ ){
  110.             wS[i] = 0;
  111.             for( j=0;j<K;j++ ){
  112.                 if( i & (1<<j) ){
  113.                     wS[i] += wei[j];
  114.                 }
  115.             }
  116.         }
  117.         CLR( vi );
  118.         long ans = Find( (1<<K)-1, 0 );
  119.         printf("%ld\n",ans );
  120.         vector<Pll> del;
  121.         printSol( (1<<K)-1, 0, del );
  122.     }
  123.  
  124.  
  125.     return 0;
  126. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement