Submission #1032962

#TimeUsernameProblemLanguageResultExecution timeMemory
1032962juicyLamps (JOI19_lamps)C++17
0 / 100
0 ms348 KiB
#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

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

	const int inf = 1e9 + 7;

	int N; string A, B; cin >> N >> A >> B;
	vector<array<int, 3>> dp(N + 1, {inf, inf, inf});
	auto match = [&](int i, int j) {
		char c = j == 2 ? A[i] : j + '0';
		return c == B[i]; 
	};
	dp[0][2] = 0;
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < 3; ++j) {
			if (dp[i][j] != inf) {
				for (int k = 0; k < 3; ++k) {
					int c = dp[i][j];
					c += j != k && k != 2;
					c += i == 0 || (match(i - 1, j) && !match(i, k));
					dp[i + 1][k] = min(dp[i + 1][k], c);
				}
			}
		}
	}
	cout << min({dp[N][0], dp[N][1], dp[N][2]});
	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...