Submission #1032970

#	Time	Username	Problem	Language	Result	Execution time	Memory
1032970		juicy	Lamps (JOI19_lamps)	C++17	100 / 100	54 ms	16296 KiB

lamp

#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;
}

• Subtask 1: 6 / 6
• Subtask 2: 41 / 41
• Subtask 3: 4 / 4
• Subtask 4: 49 / 49