Submission #738531

#	Time	Username	Problem	Language	Result	Execution time	Memory
738531		1075508020060209tc	Selotejp (COCI20_selotejp)	C++14	110 / 110	104 ms	120620 KiB

Main

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

int n;int m;
string gr[1010];
int dp[1010][12][2510];

signed main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
    cin>>gr[i];
}
for(int i=0;i<=n;i++){
    for(int j=0;j<m;j++){
        for(int A=0;A<(1<<m);A++){
            dp[i][j][A]=1e9;
        }
    }
}
dp[0][m-1][0]=0;


for(int i=0;i<=n;i++){

    for(int j=0;j<m-1;j++){

        for(int A=0;A<(1<<m);A++){
            //延伸
            if(gr[i][j+1]=='#'&& ((A&(1<<(j+1)))!=0) ){
                dp[i][j+1][A]=min(dp[i][j+1][A],dp[i][j][A]);
            }
            if(gr[i][j+1]=='#'&& ((A&(1<<(j)))==0)&&gr[i][j]=='#' ){
                int xr=0;
                if( ((A&(1<<(j+1)))!=0) ){xr+=(1<<(j+1));}
                dp[i][j+1][A^xr]=min(dp[i][j+1][A^xr],dp[i][j][A]);
            }
            //延伸

            //直接加
            if(gr[i][j+1]=='#'){
                dp[i][j+1][A|(1<<(j+1))]=min(dp[i][j+1][A|(1<<(j+1))],dp[i][j][A]+1);
            }
            if(gr[i][j+1]=='#'){
                int xr=0;
                if( ((A&(1<<(j+1)))!=0) ){xr=(1<<(j+1)); }
                dp[i][j+1][A^xr]=min(dp[i][j+1][A^xr],dp[i][j][A]+1);
            }
            //直接加
            if(gr[i][j+1]=='.'){
                int xr=0;
                if( ((A&(1<<(j+1)))!=0) ){xr=(1<<(j+1)); }
                dp[i][j+1][A^xr]=min(dp[i][j+1][A^xr],dp[i][j][A]);
            }


        }

    }
    //dp[i][m-1]
    for(int A=0;A<(1<<m);A++){
        if(gr[i+1][0]=='#'){
            if(((A&(1<<0))!=0)){
                dp[i+1][0][A^(1)]=min(dp[i+1][0][A^1],dp[i][m-1][A]+1);
                dp[i+1][0][A]=min(dp[i+1][0][A],dp[i][m-1][A]);
            }else{
                dp[i+1][0][A]=min(dp[i+1][0][A],dp[i][m-1][A]+1);
                dp[i+1][0][A|(1<<0)]=min(dp[i+1][0][A|(1<<0)],dp[i][m-1][A]+1);
            }
        }else{

            if(((A&(1<<0))==0)){
                dp[i+1][0][A]=min(dp[i+1][0][A],dp[i][m-1][A]);
            }else{
                dp[i+1][0][A^(1<<0)]=min(dp[i+1][0][A^(1<<0)],dp[i][m-1][A]);
            }
        }
    }
}
int ans=dp[n][m-1][0];
for(int A=1;A<(1<<m);A++){
    ans=min(ans,dp[n][m-1][A]);
}
cout<<ans<<endl;
return 0;
int a;int b;int c;
while(cin>>a>>b>>c){
    cout<<dp[a][b][c]<<endl;
}


}

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