제출 #1128224

#제출 시각아이디문제언어결과실행 시간메모리
1128224Alihan_8Lamps (JOI19_lamps)C++20
100 / 100
70 ms14164 KiB
#include <bits/stdc++.h>

using namespace std;

signed main(){
	int n; cin >> n;
	
	string a, b; cin >> a >> b;
	
	for ( int i = 0; i < n; i++ ){
		a[i] -= '0', b[i] -= '0';
	}
	
	auto op = [&](int x, int j){
		return j > 0 ? j - 1 : x;
	};
	
	vector <array<int,3>> dp(n);
	
	for ( int i = 0; i < n; i++ ){
		dp[i] = {n, n, n};
		
		for ( auto p: {0, 1, 2} ){
			for ( auto c: {0, 1, 2} ){
				int cnt = 0;
			
				if ( !i ) cnt = (c != 0);
				else cnt = dp[i - 1][p] + (p != c && c != 0);
				
				if ( (!i || op(a[i - 1], p) == b[i - 1]) && op(a[i], c) != b[i] ) cnt++;
				
				dp[i][c] = min(dp[i][c], cnt);
			}
		}
	}
	
	cout << min({dp[n - 1][0], dp[n - 1][1], dp[n - 1][2]}) << '\n';
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...