# CFR 788 C. The Great Mixing ( Math, bitset, DP )

Problem - C - Codeforces

The first line contains two integers n, k (0 ≤ n ≤ 1000, 1 ≤ k ≤ 1e6) — carbon dioxide concentration the friends want and the number of Coke types.
The second line contains k integers a1, a2, ..., ak (0 ≤ ai ≤ 1000) — carbon dioxide concentration of each type of Coke. Some Coke types can have same concentration.

O( N^2 * K / 32 ) / O( N )

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

const int MAXN = 1000;
const int MAXK = ( int ) 1e6;
const int MAXA = 1000;

int N, K;
int A[ MAXK ];
bitset< 1000 + 1 > dp[ 2 ];

signed main(){
ios::sync_with_stdio( 0 );
{
cin >> N >> K;
for( int i = 0; i < K; ++i ){
cin >> A[ i ];
}
sort( A, A + K );
K = unique( A, A + K ) - A;
}
{
int offset = N;
dp[ 0 ][ offset ] = 1;
for( int i = 0; i < 1000; ++i ){
dp[ ~i & 1 ].reset();
for( int j = 0; j < K; ++j ){
int t = A[ j ] - N;
if( t >= 0 ){
dp[ ~i & 1 ] |= dp[ i & 1 ] << t;
} else{
dp[ ~i & 1 ] |= dp[ i & 1 ] >> - t;
}
}
if( dp[ ~i & 1 ][ offset ] ){
cout << i + 1 << endl;
exit( 0 );
}
}
cout << -1 << endl;
}
return 0;
}
```