제출 #405694

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
405694		souvenir_vayne	Selotejp (COCI20_selotejp)	C++14	110 / 110	288 ms	62084 KiB

Main

#include<bits/stdc++.h>

using namespace std;

int l, c, dp[1005][15][1029], aux;
char m[1005][15];

int solve(int i, int j, int mask) {

    int &ans = dp[i][j][mask];

    if(ans != -1)
        return ans;

    if(j == c)
        return solve(i+1, 0, mask);
    if(i == l)
        return 0;

    int kek = 1<<j;
    if(m[i][j] == '.')
        return ans = solve(i, j+1, mask & (aux - kek));

    ans = min( solve(i, j+1, mask | kek) , solve(i, j+1, mask & (aux - kek)) ) + 1;

    if(i) {
        int now = ( mask & (1<<j) );
        if(now && m[i-1][j] == '#')
            ans = min(ans, solve(i, j+1, mask | kek));
    }

    if(j) {
        int now = mask & (1<<(j-1));
        if(!now && m[i][j-1] == '#')
            ans = min(ans, solve(i, j+1, mask & (aux - kek)));
    }


    return ans;

}

int32_t main() {


    cin >> l >> c;

    aux = (1<<c)-1;
    memset(dp, -1, sizeof dp);

    for(int i = 0; i < l; i++)
        for(int j = 0; j < c; j++)
            cin >> m[i][j];

    cout << solve(0, 0, 0) << endl;

}

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