Submission #1005271

#	Time	Username	Problem	Language	Result	Execution time	Memory
1005271		TrinhKhanhDung	Selotejp (COCI20_selotejp)	C++14	110 / 110	38 ms	57556 KiB

Main

#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define sz(x) (int)x.size()
#define ALL(v) v.begin(),v.end()
#define MASK(k) (1LL << (k))
#define BIT(x, i) (((x) >> (i)) & 1)
#define oo (ll)1e18
#define INF (ll)1e9
#define MOD (ll)(1e9 + 7)

using namespace std;

template<class T1, class T2>
    bool maximize(T1 &a, T2 b){if(a < b){a = b; return true;} return false;}

template<class T1, class T2>
    bool minimize(T1 &a, T2 b){if(a > b){a = b; return true;} return false;}

template<class T1, class T2>
    void add(T1 &a, T2 b){a += b; if(a >= MOD) a -= MOD;}

template<class T1, class T2>
    void sub(T1 &a, T2 b){a -= b; if(a < 0) a += MOD;}

template<class T>
    void cps(T &v){sort(ALL(v)); v.resize(unique(ALL(v)) - v.begin());}

const int MAXN = 1e3 + 10, MAXM = 13;

int N, M;
int a[MAXN][MAXN], f[MAXN][MAXM][MASK(10) + 10];

void solve(){
    cin >> N >> M;
    for(int i=1; i<=N; i++){
        string s; cin >> s;
        for(int j=0; j<M; j++){
            a[i][j + 1] = s[j] == '#';
        }
    }
    memset(f, 0x3f, sizeof f);
    memset(f[0][M], 0, sizeof f[0][M]);
    for(int i=1; i<=N; i++){
        for(int mask=0; mask<MASK(M); mask++){
            f[i][0][mask] = f[i - 1][M][mask];
        }

        for(int j=1; j<=M; j++){
            for(int mask=0; mask<MASK(M); mask++){
                if(!a[i][j]){f[i][j][mask] = f[i][j - 1][mask]; continue;}
                if(!BIT(mask, j - 1)){
                    if(j > 1 && !BIT(mask, j - 2) && a[i][j - 1]){
                        f[i][j][mask] = min(f[i][j - 1][mask], f[i][j - 1][mask ^ MASK(j - 1)]);
                    }
                    else{
                        f[i][j][mask] = min(f[i][j - 1][mask], f[i][j - 1][mask ^ MASK(j - 1)]) + 1;
                    }
                }
                else{
                    f[i][j][mask] = min(f[i][j - 1][mask], f[i][j - 1][mask ^ MASK(j - 1)]) + 1;
                    if(a[i - 1][j]) minimize(f[i][j][mask], f[i][j - 1][mask]);
                }
            }
        }
    }

    int ans = INF;
    for(int mask=0; mask<MASK(M); mask++){
        minimize(ans, f[N][M][mask]);
    }
    cout << ans << '\n';
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
//    freopen("netw.inp", "r", stdin);
//    freopen("netw.out", "w", stdout);

    solve();

    return 0;
}

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