Submission #54582376

---

Source Code Expand

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp> 
 
using namespace std;
using namespace __gnu_pbds;
 
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
//A.order_of_key() *A.find_by_order()
#define endl "\n"
#define int long long
#define ld long double
#define pb push_back
#define rep(i,a,b) for(int i = a; i < b; i++)
#define sz(v) v.size()
#define all(x) x.begin(),x.end()
#define in(v) for(int i = 0; i<v.size(); i++) cin>>v[i];
#define out(v) for(int i = 0; i<v.size(); i++) cout<<v[i]<<" "; cout<<endl;
#define ret(v) cout<<v<<"\n"; return
#define popcount(num) __builtin_popcount(num)
typedef vector<int> vi;
typedef pair<int,int> pii;
const int INF = 1e18;
const int MOD = 998244353;
const int N = 3e5;
const int LN = 20;

void solve(){
int n, m;
cin >> n >> m;

int dp[n + 1][(1 << m)];
for(int i = 0; i <= n; ++i){
    for(int j = 0; j < (1 << m); ++j){
        dp[i][j] = 1e9;
    }
}
dp[0][0] = 0;

for(int i = 0; i < n; ++i){
    string s;
    cin >> s;
    int string_mask = 0;
    for(int j = 0; j < m; ++j){
        if(s[j] == 'o'){
            string_mask = (string_mask | (1 << j));
        }
    }

    for(int mask = 0; mask < (1 << m); ++mask){
        dp[i + 1][mask] = min(dp[i + 1][mask], dp[i][mask]);
        dp[i + 1][string_mask | mask] = min(dp[i + 1][string_mask | mask], dp[i + 1][mask] + 1);
    }
}

cout<<(dp[n][(1 << m) - 1])<<endl;

}
 
int32_t main() {   
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0); 
    int t = 1; 
    // cin>>t;
    for(int i = 1; i<=t; i++){
        // cout<<"Case #"<<i<<": ";
        solve();
    }
    return 0;
}
 
 

Submission Info

Judge Result