제출 #535554

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
535554		MOUF_MAHMALAT	Selotejp (COCI20_selotejp)	C++14	110 / 110	166 ms	41180 KiB

Main

#include<bits/stdc++.h>
#define all(s) s.begin(),s.end()
#define F first
#define S second
using namespace std;
typedef int ll;
ll n,m,dp[10][1000][1<<10],o;
bool b[1000][10];
ll best(ll j,ll d,ll mask)
{
    if(j==m)
    {
        j=0;
        d++;
    }
    if(d==n)
        return 0;
    ll &r=dp[j][d][mask];
    if(r!=-1)
        return r;
    if(!b[d][j])
        return r=best(j+1,d,mask&(o^(1<<j)));
    if(j&&((mask&(1<<(j-1)))==0)&&b[d][j-1])
        r=best(j+1,d,mask&(o^(1<<j)));
    else
        r=best(j+1,d,mask&(o^(1<<j)))+1;
    if((mask&(1<<j))!=0)
        r=min(r,best(j+1,d,mask));
    else
        r=min(r,best(j+1,d,mask|(1<<j))+1);
    return r;
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(ll i=0; i<n; i++)
        for(ll j=0; j<m; j++)
        {
            char c;
            cin>>c;
            if(c=='#')
                b[i][j]=1;
        }
    o=(1<<m)-1;
    memset(dp,-1,sizeof dp);
    cout<<best(0,0,0);
    return 0;
}

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