1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4  5 using namespace std; 6 #define N 1005 7 int state[N] , n , m , dp[N][1<<6]; 8  9 void dfs(int i , int k , int state1 , int state2 , int v)10 {11     if(k > 5){12         dp[i][state2] = max(dp[i][state2] , v);13         return;14     }15     if(k <= 4){16         if(!(state1&(1<<k-1)) && !(state2&(3<<k-1))){17             dfs(i , k+1 , state1 | (1<<k-1) , state2 | (3<<k-1) , v+3);18         }19         if(!(state1&(1<<k)) && !(state2&(3<<k-1))){20             dfs(i , k+1 , state1 | (1<<k) , state2 | (3<<k-1) , v+3);21         }22         if(!(state1&(3<<k-1)) && !(state2&(1<<k-1))){23             dfs(i , k+1 , state1 | (3<<k-1) , state2 | (1<<k-1) , v+3);24         }25         if(!(state1&(3<<k-1)) && !(state2&(1<<k))){26             dfs(i , k+1 , state1 | (3<<k-1) , state2 | (1<<k) , v+3);27         }28         if(!(state2&(3<<k-1))){29             dfs(i , k+1 , state1 , state2 | (3<<k-1) , v+2);30         }31     }32     else{33         if(!(state1&(1<<k-1)) && !(state2&(1<<k-1))){34             dfs(i , k+1 , state1 | (1<<k-1) , state2 | (1<<k-1) , v+2);35         }36     }37     dfs(i , k+1 , state1 , state2 , v);38 }39 40 void dfs2(int k , int sta , int v)41 {42     if(k > 5){43         dp[1][sta] = max(dp[1][sta] , v);44         return;45     }46     if(k <= 4){47         if(!(sta & (3<<k-1)))48             dfs2(k+1 , sta | (3<<k-1) , v+2);49     }50     dfs2(k+1 , sta , v);51 }52 53 int main()54 {55   //  freopen("a.in" , "rb" , stdin);56     char a;57     while(scanf("%d%d", &n , &m) != EOF){58         memset(state , 0 ,sizeof(state));59         int all = 0;60         for(int i = 1; i <= n ; i++)61             for(int j=1; j<=5 ; j++){62                 cin>>a;63                 if(a == ‘1‘){64                     state[i] |= (1<<j-1);65                 }66                 else all++;67             }68 69         memset(dp , -1 , sizeof(dp));70         dp[1][state[1]] = 0;71         dfs2(1 , state[1] , 0);72 73         for(int i=2 ; i <= n ; i++){74             for(int j = 0; j<(1<<5) ; j++){75                 if(dp[i-1][j] >= 0){76                     dfs(i , 1 , j , state[i] , dp[i-1][j]);77                 }78             }79         }80 81         int maxn = 0;82 83         for(int i = 0 ; i<(1<<5) ; i++){84             maxn = max(maxn , dp[n][i]);85         }86 87         int remain = all - maxn;88         if(remain <= m) puts("YES");89         else puts("NO");90     }91     return 0;92 }