제출 #159663

#제출 시각아이디문제언어결과실행 시간메모리
159663DiuvenLamps (JOI19_lamps)C++14
100 / 100
32 ms16120 KiB
#include <bits/stdc++.h>
using namespace std;

const int MAX = 1e6+10;
inline int f(int a, int b){ return a<b ? a : b; }

int n, D[MAX][3]; // 0 1 x
char A[MAX], B[MAX];

int main(){
	ios::sync_with_stdio(0); cin.tie(0);

	cin>>n>>(A+1)>>(B+1);
	D[1][0] = 1 + (B[1]!='0');
	D[1][1] = 1 + (B[1]!='1');
	D[1][2] = 0 + (B[1]!=A[1]);

	for(int i=2; i<=n; i++){
		int &z=D[i-1][0], &o=D[i-1][1], &x=D[i-1][2];
		int b=B[i]=='1';
		D[i][0] = f(z + (b && B[i-1]=='0'), x + 1 + (b && A[i-1]==B[i-1]));
		D[i][1] = f(o + (!b&& B[i-1]=='1'), x + 1 + (!b&& A[i-1]==B[i-1]));
		D[i][2] = f(f(
			z + (A[i]!=B[i] && B[i-1]=='0'),
			o + (A[i]!=B[i] && B[i-1]=='1')),
			x + (A[i]!=B[i] && A[i-1]==B[i-1]));
	}

	cout<<f(f(D[n][0], D[n][1]), D[n][2])<<'\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...