Submission #102131

#TimeUsernameProblemLanguageResultExecution timeMemory
102131tpoppoLamps (JOI19_lamps)C++14
4 / 100
67 ms25972 KiB
#include <bits/stdc++.h>
 
using namespace std;
const int MAXN = 1e6 + 100;
int n;
string a,b;
 
int dp[MAXN][2][3];
 
int main() {
	cin.tie(0);
	ios::sync_with_stdio(0);
	cin >> n;
	cin >> a >> b;
	memset(dp,0x66,sizeof(dp));
	
	
	for(int inv=0;inv<2;inv++) {
		for(int z=0;z<3;z++) {
			dp[0][inv][z] = (inv == 1) + (z != 2);
		}
	}
	
	for(int i=0;i<=n;i++) {
		for(int inv=0;inv<2;inv++) {
			for(int z=0;z<3;z++) {
 
				//cout<<setw(10)<<dp[i][inv][z]<<" ";
				if(b[i] == '0') {
					dp[i+1][0][0] = min(dp[i+1][0][0],dp[i][inv][z] + (z != 0) );
					dp[i+1][1][0] = min(dp[i+1][1][0],dp[i][inv][z] + (z != 0) + (inv != 1) );
				}
 
				if(b[i] == '1'){
					dp[i+1][0][1] = min(dp[i+1][0][1],dp[i][inv][z] + (z != 1) );
					dp[i+1][1][1] = min(dp[i+1][1][1],dp[i][inv][z] + (z != 1)  + (inv != 1) );
				
				}
				if(b[i] == a[i]) dp[i+1][0][2] = min(dp[i+1][0][2],dp[i][inv][z]  );
				else dp[i+1][1][2] = min(dp[i+1][1][2],dp[i][inv][z] + (inv != 1) );
			}
		}//cout<<endl;
	}
	int rs = 1e9;
	for(int inv=0;inv<2;inv++) {
		for(int z=0;z<3;z++) {
			rs = min(rs,dp[n][inv][z]);
		}
	}
 
	cout<<rs<<'\n';
 
	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...