Submission #435715

#TimeUsernameProblemLanguageResultExecution timeMemory
435715dutchLamps (JOI19_lamps)C++17
100 / 100
49 ms4472 KiB
#include <bits/stdc++.h>
using namespace std;
#define int long long

const int INF = 1e18;

void r(int &a, int b){ a = min(a, b); }

signed main(){
	cin.tie(0)->sync_with_stdio(0);
	int n; string a, b; cin >> n >> a >> b;
	array<int, 3> dp = {0, INF, INF}, c;

	for(int i=0; i<n; ++i){
		c = {INF, INF, INF};
		array<bool, 3> prev = {b[i-1] != a[i-1], b[i-1] == '1', b[i-1] == '0'};
		array<bool, 3> curr = {b[i] != a[i], b[i] == '1', b[i] == '0'};
		for(int j=0; j<3; ++j){
			for(int k=0; k<3; ++k){
				int cost = (k && k!=j) + (curr[k] && curr[k] != prev[j]);
				r(c[k], dp[j] + cost);
			}
		}
		swap(c, dp);
	}

	cout << min(dp[0], min(dp[1], dp[2]));
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...