Submission #540114

#	Time	Username	Problem	Language	Result	Execution time	Memory
540114		valerikk	Lamps (JOI19_lamps)	C++17	100 / 100	135 ms	65072 KiB

lamp

#include <bits/stdc++.h>

using namespace std;

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

	int n;
	cin >> n;
	
	auto read = [&]() {
		string s;
		cin >> s;
		vector<int> res(n);
		for (int i = 0; i < n; ++i) {
			res[i] = s[i] - '0';
		}
		return res;
	};

	auto a = read();
	auto b = read();

	vector<vector<int>> dp(n, vector<int>(3, numeric_limits<int>::max()));
	for (int x = 0; x < 3; ++x) {
		int c = b[0] ^ (x == 2 ? a[0] : x);
		dp[0][x] = c + (x != 2);
	}
	for (int i = 0; i < n - 1; ++i) {
		for (int x = 0; x < 3; ++x) {
			int xx = b[i] ^ (x == 2 ? a[i] : x);
			for (int y = 0; y < 3; ++y) {
				int yy = b[i + 1] ^ (y == 2 ? a[i + 1] : y);
				dp[i + 1][y] = min(dp[i + 1][y], dp[i][x] + (y != x && y != 2) + (yy == 1 && xx == 0));
			}
		}
	}
	
	cout << *min_element(dp[n - 1].begin(), dp[n - 1].end()) << endl;
	
	return 0;
}

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