oj.uz

Submission #991004

# Submission time Handle Problem Language Result Execution time Memory
991004 2024-06-01T03:58:22 Z amirhoseinfar1385 Selotejp (COCI20_selotejp) C++17
35 / 110
 1 ms 604 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 604 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 484 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 604 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -