제출 #1012388

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1012388		vjudge1	Selotejp (COCI20_selotejp)	C++17	110 / 110	15 ms	488 KiB

Main

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

#define ll long long
int const N=1030;
int const inf=1e9;

int dp[N],cur[N];
string s[N];
int main(){
	int n,m;
	cin>>n>>m;
	for (int i = 1; i < N; ++i){
		dp[i]=inf;
		cur[i]=inf;
	}
	dp[0]=0;
	cur[0]=inf;
	for (int i = 0; i < n; ++i)
		cin>>s[i];
	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(s[i][j]=='.')
						cur[mask]=inf;
					else
						cur[mask]=min(dp[mask],dp[mask ^ (1<<j)]+1);
				}
				else{
					cur[mask]=min(dp[mask],dp[mask^(1<<j)]);
					if(s[i][j] == '#' && (j == 0 || (mask & (1 << (j - 1))) || s[i][j - 1] == '.'))
						cur[mask]++;
				}
			}
			for (int mask = 0; mask < (1<<m); ++mask)
				dp[mask]=cur[mask];
		} 
	}
	int ans=inf;
	for (int i = 0; i < (1<<m); ++i)
		ans=min(ans,dp[i]);
	cout<<ans<<endl;
	return 0;
}

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