Submission #991004

#	Time	Username	Problem	Language	Result	Execution time	Memory
991004		amirhoseinfar1385	Selotejp (COCI20_selotejp)	C++17	35 / 110	1 ms	604 KiB

Main

#include<bits/stdc++.h>
using namespace std;
const int maxn=10,maxm=1000;
int all[maxn][maxm],dp0[(1<<maxn)],dp1[(1<<maxn)],n,m;

void vorod(){
	cin>>n>>m;
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			char c;
			cin>>c;
			if(c=='#'){
				all[i][j]=1;
			}else{
				all[i][j]=0;
			}
		}
	}
}

void solve(){
	for(int i=0;i<(1<<n);i++){
		for(int j=0;j<n;j++){
			if(all[j][0]==0){
				continue;
			}
			if((i>>j)&1){
				dp0[i]++;
			}else{
				if(j==0||all[j-1][0]==0||((i>>(j-1))&1)==1){
					dp0[i]++;
				}
			}
		}
	}
	for(int j=1;j<m;j++){
		for(int i=0;i<n;i++){
			for(int mask=0;mask<(1<<n);mask++){
				if(all[i][j]==0){
					dp1[mask]=min(dp0[mask],dp0[mask^(1<<i)]);
				}else{
					if(((mask>>i)&1)==1){
						if(all[i][j-1]==0){
							dp1[mask]=dp0[mask]+1;
						}else{
							dp1[mask]=min(dp0[mask],dp0[mask^(1<<i)]+1);
						}
					}else{
						if(i==0||all[i-1][j]==0||((mask>>(i-1))&1)==1){
							dp1[mask]=min(dp0[mask],dp0[mask^(1<<i)])+1;
						}else{
							dp1[mask]=min(dp0[mask],dp0[mask^(1<<i)]);
						}
					}
				}
			}
			for(int mask=0;mask<(1<<n);mask++){
				dp0[mask]=dp1[mask];
				dp1[mask]=0;
			}
		}
	}
	int res=n*m;
	for(int mask=0;mask<(1<<n);mask++){
		res=min(res,dp0[mask]);
	}
	cout<<res<<"\n";
}

int main(){
	vorod();
	solve();
}

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