제출 #1370062

#제출 시각아이디문제언어결과실행 시간메모리
1370062kaiboyLamps (JOI19_lamps)C++20
100 / 100
50 ms2384 KiB
#include <algorithm>
#include <iostream>

using namespace std;

const int   N = 1000000;
const int INF = 0x3f3f3f3f;

char aa[N + 1], bb[N + 1];
int dp[2][2][3], dq[2][2][3];

int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL);
	int n; cin >> n >> aa >> bb;
	for (int s = 0; s < 2; s++)
		for (int t = 0; t < 2; t++)
			for (int a = 0; a <= 2; a++)
				dp[s][t][a] = INF;
	dp[0][0][2] = 0;
	for (int i = 0; i < n; i++) {
		for (int s = 0; s < 2; s++)
			for (int t = 0; t < 2; t++)
				for (int a = 0; a <= 2; a++)
					dq[s][t][a] = INF;
		for (int s = 0; s < 2; s++)
			for (int t = 0; t < 2; t++)
				for (int a = 0; a <= 2; a++)
					for (int s_ = 0; s_ < 2; s_++) {
						int x = dp[s][t][a];
						if (!s && s_)
							x++;
						int b = bb[i] - '0' ^ s_;
						if (aa[i] - '0' == b)
							dq[s_][0][2] = min(dq[s_][0][2], x);
						if (a != b) {
							int t_ = t ^ 1;
							dq[s_][t_][b] = min(dq[s_][t_][b], x + t + (a == 2));
						} else
							dq[s_][t][b] = min(dq[s_][t][b], x);
					}
		for (int s = 0; s < 2; s++)
			for (int t = 0; t < 2; t++)
				for (int a = 0; a <= 2; a++)
					dp[s][t][a] = dq[s][t][a];
	}
	int ans = INF;
	for (int s = 0; s < 2; s++)
		for (int t = 0; t < 2; t++)
			for (int a = 0; a <= 2; a++)
				ans = min(ans, dp[s][t][a]);
	cout << ans << '\n';
	return 0;
}
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…