Submission #684387

#	Time	Username	Problem	Language	Result	Execution time	Memory
684387		vjudge1	Selotejp (COCI20_selotejp)	C++17	0 / 110	12 ms	6076 KiB

Main

#include <bits/stdc++.h>
#define ll long long
using namespace std;

const int INF = 2e9;
int dp[1001][11][(1<<11)];
char grid[1001][11];
int main()
{
    
    int n, m;
    cin>>n>>m;
    for(int i = 0; i < n; i++) for (int j = 0; j < m; j++) for (int mask = 0; mask < (1<<m); mask++) dp[i][j][mask] = INF;
    for(int i = 0; i < n; i++){
        for (int j = 0; j < m; j++)
        {
            cin>>grid[i][j];
        }
    }
    for(int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            for (int mask = 0; mask < (1<<m); mask++)
            {
                if(mask & (1<<j)){
                    if(grid[i][j] == '.') dp[i][j][mask] = INF;
                    else dp[i][j][mask] = min(dp[i][j - 1][mask], dp[i][j - 1][(mask ^ (1<<j))] + 1);
                }else{
                    dp[i][j][mask] = min(dp[i][j - 1][mask], dp[i][j - 1][(mask ^ (1<<j))]);
                    if(grid[i][j] == '#' && (j == 0 || grid[i][j - 1] || (mask & (1<<(j - 1))))) dp[i][mask][j]++;
                }
            }
        }
        for (int mask = 0; mask < (1<<n); mask++) dp[i + 1][0][mask] = dp[i][m - 1][mask];
    }
    cout<<*min_element(dp[n - 1][m - 1], dp[n - 1][m - 1] + (1<<m));
}

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