Submission #542043

#	Time	Username	Problem	Language	Result	Execution time	Memory
542043		AlperenT	Selotejp (COCI20_selotejp)	C++17	110 / 110	44 ms	40396 KiB

Main

#include <bits/stdc++.h>

using namespace std;

const int N = 1000 + 5, M = 10, K = 1 << M;

int n, m, dp[N][M][K];

char arr[N][M];

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

    cin >> n >> m;

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

    for(int i = 1; i <= n; i++){
        for(int j = 0; j < m; j++){
            for(int msk = 0; msk < (1 << m); msk++){
                if(j == 0){
                    if(msk & (1 << j)){
                        dp[i][j][msk] = min(dp[i - 1][m - 1][msk] + (arr[i][j] == '#' && arr[i - 1][j] != '#'), dp[i - 1][m - 1][msk ^ (1 << j)] + (arr[i][j] == '#'));
                    }
                    else{
                        dp[i][j][msk] = min(dp[i - 1][m - 1][msk], dp[i - 1][m - 1][msk ^ (1 << j)]) + (arr[i][j] == '#');
                    }
                }
                else{
                    if(msk & (1 << j)){
                        dp[i][j][msk] = min(dp[i][j - 1][msk] + (arr[i][j] == '#' && arr[i - 1][j] != '#'), dp[i][j - 1][msk ^ (1 << j)] + (arr[i][j] == '#'));
                    }
                    else{
                        if(!(msk & (1 << (j - 1)))){
                            dp[i][j][msk] = min(dp[i][j - 1][msk], dp[i][j - 1][msk ^ (1 << j)]) + (arr[i][j] == '#' && arr[i][j - 1] != '#');
                        }
                        else{
                            dp[i][j][msk] = min(dp[i][j - 1][msk], dp[i][j - 1][msk ^ (1 << j)]) + (arr[i][j] == '#');
                        }
                    }
                }
            }
        }
    }

    cout << *min_element(dp[n][m - 1], dp[n][m - 1] + (1 << m));
}

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