# ZOJ 3280 Choose The Best ( Bitmask )

ZOJ :: Problems :: Show Problem

There are no more than 15 cases. Process to the end of file.
For each case, the first line contains two integers n (2 <= n <= 50000) and m (1 <= m <= 8). Then n lines follow and each line contains m integers to specify the n combos. The next line contains m integers means the weights for the nutrients. It is guaranteed that there exist at least two different combos. All weights are positive numbers and no more than 100. All elements in the n m-tuples are positive and no more than 1000.

O( N * 2^M )

```#include <bits/stdc++.h>
using namespace std;

signed main(){
ios::sync_with_stdio( 0 );
int N, M;
while( cin >> N >> M ){
vector< vector< int > > combo( N, vector< int >( M ) );
for( int i = 0; i < N; ++i ){
for( int j = 0; j < M; ++j ){
cin >> combo[ i ][ j ];
}
}
vector< int > wei( M );
for( int i = 0; i < M; ++i ){
cin >> wei[ i ];
}
int ans = 0;
vector< int > mask_min( 1 << M, 1 << 28 );
for( int i = 0; i < N; ++i ){
for( int j = 0; j < 1 << M; ++j ){
int sum = 0;
for( int k = 0; k < M; ++k ){
if( j >> k & 1 ){
sum += wei[ k ] * combo[ i ][ k ];
} else{
sum -= wei[ k ] * combo[ i ][ k ];
}
}
ans = max( ans, sum - mask_min[ j ] );