# CFR 339 C. Xenia and Weights ( DP )

Problem - C - Codeforces

```string seq;
int M;

void init(){
cin >> seq;
cin >> M;
}

const int INF = 0x3f3f3f3f;
const int ZERO = 10;

vi C;
vvi dp;
vvi pre;

void preprocess(){
for( int i = 0; i < 10; ++i )
if( seq[ i ] == '1' )
C.push_back( i + 1 );
dp = vvi( M + 1, vi( ZERO * 2 + 1 ) );
dp[ 0 ][ ZERO ] = 1;
pre = vvi( M + 1, vi( ZERO * 2 + 1, INF ) );
for( int i = 0; i < M; ++i ){
for( int j = 0; j <= 20; ++j ) if( dp[ i ][ j ] ){
for( int c : C ){
if( abs( pre[ i ][ j ] - j ) == c )
continue;
if( j == ZERO ){
if( j + c <= 20 and upmax( dp[ i + 1 ][ j + c ], 1 ) )
pre[ i + 1 ][ j + c ] = j;
if( 0 <= j - c and upmax( dp[ i + 1 ][ j - c ], 1 ) )
pre[ i + 1 ][ j - c ] = j;
} else if( j < ZERO ){
if( ZERO < j + c and j + c <= 20 and upmax( dp[ i + 1 ][ j + c ], 1 ) )
pre[ i + 1 ][ j + c ] = j;
} else{
if( 0 <= j - c and j - c < ZERO and upmax( dp[ i + 1 ][ j - c ], 1 ) )
pre[ i + 1 ][ j - c ] = j;
}
}
}
}
}

void solve(){
for( int i = 0; i <= 20; ++i )
if( dp[ M ][ i ] ){
cout << "YES" << endl;
stack< int > ans;
for( int m = M, u = i; pre[ m ][ u ] != INF; u = pre[ m ][ u ], --m )
ans.push( abs( u - pre[ m ][ u ] ) );
for( ; not ans.empty(); ans.pop() )
cout << ans.top() << " \n"[ ( int ) ans.size() == 1 ];
return;
}
cout << "NO" << endl;
}
```