제출 #1125626

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1125626		Zero_OP	Selotejp (COCI20_selotejp)	C++17	110 / 110	72 ms	45128 KiB

Main

#include <bits/stdc++.h>

using namespace std;

template<typename T>
bool minimize(T& a, const T& b){
    if(a > b) return a = b, true;
    return false;
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);

#ifdef LOCAL
    freopen("task.inp", "r", stdin);
    freopen("task.out", "w", stdout);
#endif // LOCAL

    int N, M;
    cin >> N >> M;

    vector<vector<char>> a(N, vector<char>(M));
    for(int i = 0; i < N; ++i){
        for(int j = 0; j < M; ++j){
            cin >> a[i][j];
        }
    }

    const int inf = 1e9;
    vector<vector<vector<int>>> f(N + 1, vector<vector<int>>(M + 1, vector<int>(1 << M, inf)));

    f[0][0][0] = 0;

    //mask : use to horizontal tapes some rows

    for(int i = 0; i < N; ++i){
        for(int j = 0; j < M; ++j){
            for(int mask = 0; mask < (1 << M); ++mask){
                if(f[i][j][mask] == inf) continue;

                if(a[i][j] == '#'){
                    if(mask >> j & 1){
                        minimize(f[i][j + 1][mask], f[i][j][mask]);
                    } else{
                        minimize(f[i][j + 1][mask ^ (1 << j)], f[i][j][mask] + 1);
                    }

                    int rem = min(mask, mask ^ (1 << j));
                    if(j > 0 && (a[i][j - 1] == '#') && (mask >> (j - 1) & 1 ^ 1)){
                        minimize(f[i][j + 1][rem], f[i][j][mask]);
                    } else{
                        minimize(f[i][j + 1][rem], f[i][j][mask] + 1);
                    }
                } else{
                    if(mask >> j & 1){
                        minimize(f[i][j + 1][mask ^ (1 << j)], f[i][j][mask]);
                    } else{
                        minimize(f[i][j + 1][mask], f[i][j][mask]);
                    }
                }
            }
        }

        for(int mask = 0; mask < (1 << M); ++mask){
            f[i + 1][0][mask] = f[i][M][mask];
        }
    }

    int ans = inf;
    for(int mask = 0; mask < (1 << M); ++mask){
        ans = min(ans, f[N][0][mask]);
    }
    cout << ans << '\n';

    return 0;
}

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