Submission #1101836

#	Time	Username	Problem	Language	Result	Execution time	Memory
1101836		phamducminh	Selotejp (COCI20_selotejp)	C++17	110 / 110	261 ms	9304 KiB

Main

#include <bits/stdc++.h>
#include <iostream>
#include <cmath>
#include <vector>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <stack>
#include <algorithm>
#include <string>
#include <queue>
#include <cctype>
#include <cstring>
#include <iomanip>
#include <deque>
#include <random>
#include <sstream>

// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")
// #pragma GCC optimize("Ofast","inline","no-stack-protector")


using namespace std;

#define file(name) freopen(name".inp","r",stdin);\
                    freopen(name".out","w",stdout);
#define TIME (1.0*clock()/CLOCKS_PER_SEC)
#define all(a) a.begin(),a.end()
#define all1(a) a+1,a+n+1
#define ll long long

const long long INF=1e18;
const long long MOD=1e9+7;
const long long MODD=998244353; // 998244353
const int maxN=1e6+9;
const short LOG=20;


//------------------------



void solve();
signed main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);


    // file("boat");



    int t;

    // cin >> t;

    t=1;

    while (t--){
        solve();
    }


    return 0;
}

/// -------------- PROBLEM SOLUION --------------------


#define int ll

char a[1009][19];
int n,m;

long long dp[1009][1100];
long long cost(int i, int mask){
    long long ans=0;
    for (int j=1; j<=m; j++){
        if (((mask>>(j-1))&1) == 0) {
            if (a[i][j]=='.') continue;

            if (j==1 || a[i][j-1]=='.' || ((mask>>(j-2))&1)) ans++;
        }
    }
    return ans;
}
void solve(){


    
    cin >> n >> m;

    for (int i=1; i<=n; i++){
        for (int j=1; j<=m; j++){
            cin >> a[i][j];
        }
    }


    // dp[i][mask] bit[j] = 0/1 la hang j duoc dan hoac cot j duoc dan
    memset(dp,0x3f,sizeof dp);
    dp[0][0]=0;

    for (int i=1; i<=n; i++){
        for (int mask=0; mask<(1<<m); mask++){
            int ok=1;
            for (int j=1; j<=m; j++){
                if (((mask>>(j-1))&1) && a[i][j]=='.') ok=0;
            }

            if (!ok) continue;



            // for bit con
            for (int nmask = mask;; nmask = (nmask - 1) & mask){
                dp[i][mask]=min(dp[i][mask],dp[i-1][nmask] + __builtin_popcount(nmask^mask));
                if (!nmask) break;
            }

            dp[i][mask]+=cost(i,mask);

            for (int nmask = mask;; nmask = (nmask - 1) & mask){
                dp[i][nmask]=min(dp[i][nmask],dp[i][mask]);
                if (!nmask) break;
            }


        }
    }




    long long ans=INF;
    for (int mask=0; mask<(1<<m); mask++){
        ans=min(ans,dp[n][mask]);

        // cout << dp[n][mask] << "\n";
    }

    cout << ans;

}
 
 

• Subtask 1: 35 / 35
• Subtask 2: 35 / 35
• Subtask 3: 40 / 40