Submission #1154449

#	Time	Username	Problem	Language	Result	Execution time	Memory
1154449		i271828	Selotejp (COCI20_selotejp)	C++20	110 / 110	40 ms	40516 KiB

Main

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

int N=2;
int M=3;
bool A[1005][10]={{1,0,1},{1,1,1}};
int dp[10005][1030];
// 1 3 ###
int main(){
	cin>>N>>M;
	for (int i=0;i<N;i++){
		for (int j=0;j<M;j++){
			char c;
			cin>>c;
			if (c=='#') A[i][j]=1;
			else A[i][j]=0;
		}
	}
	
	for (int x=0;x<(1<<M);x++){
		dp[0][x]=A[0][0] ? 1 : 0;
	}
	
	int i=0,j=0;
	for (int p=1;p<(N*M);p++){
		j++;
		if (j==M) j=0,i++;
		for (int x=0;x<(1<<M);x++){
			int nx0=x>>1;
			int nx1=(x>>1)|(1<<(M-1));
			
			if (!A[i][j]){
				dp[p][x]=min(dp[p-1][nx0], dp[p-1][nx1]);
				continue;
			}else{
				dp[p][x]=min(dp[p-1][nx0], dp[p-1][nx1]) + 1;
				
				if (j>0 && A[i][j-1] && (x&3)==0){
					//cout<<'-'<<' ';
					int v=min(dp[p-1][nx0],dp[p-1][nx1]);
					dp[p][x]=min(dp[p][x], v);
				}
				if (i>0 && A[i-1][j] && x&1){
					//cout<<'|'<<' ';
					int v=dp[p-1][nx1];
					dp[p][x]=min(dp[p][x], v);
				}
			}
			//cout<<i<<' '<<j<<' '<<x<<' '<<dp[p][x]<<'\n';
		}
	}
	int ans=1<<30;
	for (int x=0;x<(1<<M);x++){
		ans=min(ans,dp[N*M-1][x]);
	}
	cout<<ans;
}

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