Submission #220607

#	Time	Username	Problem	Language	Result	Execution time	Memory
220607		atoiz	Lamps (JOI19_lamps)	C++14	100 / 100	43 ms	4552 KiB

lamp

#include <iostream>
#include <vector>
#include <algorithm>
#include <array>

using namespace std;

const int MAXN = 1000007;
int N;
string A, B;
int dp[2][3];
bool toggle[2][3];

void minimize(int &x, int y) { x = (x < y ? x : y); }

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> N >> A >> B;

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

	for (int i = 0; i < N; ++i) {
		bool k = i & 1;
		dp[k ^ 1][0] = dp[k ^ 1][1] = dp[k ^ 1][2] = MAXN;

		toggle[k ^ 1][0] = (B[i] == '1'), toggle[k ^ 1][1] = (B[i] == '0'), toggle[k ^ 1][2] = (A[i] != B[i]);

		for (int x = 0; x < 3; ++x) {
			for (int y = 0; y < 3; ++y) {
				minimize(dp[k ^ 1][y], dp[k][x] + (x != y && y != 2) + (toggle[k][x] == 0 && toggle[k ^ 1][y] == 1));
			}
		}
	}

	cout << min({dp[N & 1][0], dp[N & 1][1], dp[N & 1][2]}) << endl;
}

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