Submission #1222246

#TimeUsernameProblemLanguageResultExecution timeMemory
1222246thangdz2k7Lamps (JOI19_lamps)C++20
100 / 100
31 ms14060 KiB
#include <bits/stdc++.h>

using namespace std;

auto minl(int &a, int b){
	a = min(a, b);
}

const int MAX = 1e6 + 5;
const int inf = 1e9;

int n, dp[MAX][3];
// 0 : off
// 1 : on
// 2 : non 

string a, b;

void process(){
	cin >> n;
	cin >> a >> b;
	a = ' ' + a, b = ' ' + b;

	dp[0][0] = inf, dp[0][1] = inf, dp[0][2] = 0;

	for (int i = 1; i <= n; ++ i){
		int tar = b[i] - '0';
		for (int j : {0, 1, 2}) dp[i][j] = inf;

		for (int j : {0, 1, 2}) if (dp[i - 1][j] != inf){
			int tmp = dp[i - 1][j];
			int tog = 0;

			if (i > 1){
				int las = j;
				if (j > 1) las = a[i - 1] - '0';
				int g = b[i - 1] - '0';
				tog = (las != g);
			}

			for (int k : {0, 1, 2}){
				if (k != j && max(k, j) < 2) continue;
				int cur = k;
				if (cur > 1) cur = a[i] - '0';
				minl(dp[i][k], tmp + (k < 2 && j == 2) + (!tog && cur != tar));
			}
		}

		//cout << dp[i][0] << ' ' << dp[i][1] << ' ' << dp[i][2] << endl;
	}

	cout << min({dp[n][0], dp[n][1], dp[n][2]});
}

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

	process();
	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...