제출 #1265963

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1265963		luuthanhdatbienhoak66	Selotejp (COCI20_selotejp)	C++20	110 / 110	12 ms	460 KiB

Main

#include "bits/stdc++.h"
using namespace std;
#define ll long long
const int inf=1e9+7;

char a[1002][12];

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

    int n,m;
    cin>>n>>m;

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

    vector<int> dp(1<<m,inf);
    vector<int> prev(1<<m);
    dp[0]=0;

    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            for(int k=0;k<(1<<m);k++)
            {
                if(k&(1<<j))
                {
                    if(a[i][j]=='.') prev[k]=inf;
                    else prev[k]=min(dp[k],dp[k^(1<<j)]+1);
                }
                else
                {
                    prev[k]=min(dp[k],dp[k^(1<<j)]);
                    if(a[i][j]=='#' && (j==0 || (k&(1<<(j-1))) || a[i][j-1]=='.'))
                    {
                        prev[k]++;
                    }
                }
            }
            dp=prev;
        }
    }

    cout<<*min_element(dp.begin(),dp.end());

    return 0;
}

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