Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #pragma comment(linker, "/STACK:16777216")
- #include <bits/stdc++.h>
- using namespace std;
- #define CLR(a) memset(a,0,sizeof(a))
- #define SET(a) memset(a,-1,sizeof(a))
- #define pb push_back
- #define SZ(a) ((long)a.size())
- #define ALL(a) a.begin(),a.end()
- #define FOREACH(i, c) for( __typeof( (c).begin() ) i = (c).begin(); i != (c).end(); ++i )
- #define AREA2(x1,y1,x2,y2,x3,y3) ( x1*(y2-y3) + x2*(y3-y1) + x3*(y1-y2) )
- #define SQR(x) ((x)*(x))
- #define STR string
- #define IT iterator
- #define ff first
- #define ss second
- #define MP make_pair
- #define EPS 1e-9
- #define INF 1000000007
- #define chk(a,k) ((bool)(a&(1<<(k))))
- #define set0(a,k) (a&(~(1<<(k))))
- #define set1(a,k) (a|(1<<(k)))
- typedef long long Long;
- typedef vector<long> Vl;
- typedef vector<Long> VL;
- typedef pair<long,long> Pll;
- typedef pair<Long,Long> PLL;
- inline long FastMax(long x, long y) { return (((y-x)>>(32-1))&(x^y))^y; }
- inline long FastMin(long x, long y) { return (((y-x)>>(32-1))&(x^y))^x; }
- long IR[] = { 0,-1,0,1,-1,-1,1,1 };
- long IC[] = { 1,0,-1,0,1,-1,-1,1 };
- #define MAX 10
- long N,K;
- long cap[MAX+7];
- long wei[MAX+7];
- long wS[1<<MAX];
- bool vi[1<<MAX][MAX+7];
- long sol[1<<MAX][MAX+7];
- long st[1<<MAX][MAX+7];
- long Find( long b, long t ){
- if( !b ) return 0;
- if( vi[b][t] ) return sol[b][t];
- vi[b][t] = true;
- sol[b][t] = INF;
- long subs = b;
- while( 1 ){
- if( wS[subs] <= cap[t] ){
- long tmp = Find( b & ~subs, (t+1)%N );
- if( tmp < sol[b][t] ){
- sol[b][t] = tmp;
- st[b][t] = subs;
- }
- }
- if( !subs ) break;
- subs = (subs-1) & b;
- }
- return sol[b][t] = sol[b][t] + (t==0);
- }
- void printSol( long b, long t, vector<Pll> &del ){
- long i;//printf("%ld %ld\n",b,t );
- if( (t==0 or !b) and del.size() ){
- printf("%ld",del.size() );
- for( i=0;i<del.size();i++ ){
- printf(" %ld %ld",del[i].ff, del[i].ss );
- }
- printf("\n");
- del.clear();
- }
- if( !b ) return;
- for( i=0;i<K;i++ ){
- if( st[b][t] & (1<<i ) ){
- del.pb( MP( (i+1),( t+1 ) ) );
- }
- }
- printSol( b & ~st[b][t], (t+1)%N, del );
- }
- int main( void )
- {
- long i,j,Icase,k=0;
- //freopen("text1.txt","r",stdin );
- freopen("dhl.in","r",stdin );
- freopen("dhl.out","w",stdout );
- while( cin>>N>>K ){
- long mC = 0;
- for( i=0;i<N;i++ ){
- cin>>cap[i];
- mC = max( mC, cap[i] );
- }
- long mW = 0;
- for( i=0;i<K;i++ ){
- cin>>wei[i];
- mW = max( mW, wei[i] );
- }
- if( mC < mW ){
- printf("-1\n");
- continue;
- }
- for( i=0;i<(1<<K);i++ ){
- wS[i] = 0;
- for( j=0;j<K;j++ ){
- if( i & (1<<j) ){
- wS[i] += wei[j];
- }
- }
- }
- CLR( vi );
- long ans = Find( (1<<K)-1, 0 );
- printf("%ld\n",ans );
- vector<Pll> del;
- printSol( (1<<K)-1, 0, del );
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement