Submission #445727

#	Time	Username	Problem	Language	Result	Execution time	Memory
445727		egod1537	Lamps (JOI19_lamps)	C++14	4 / 100	23 ms	8320 KiB

lamp

#include <bits/stdc++.h>

using namespace std;

int dp[1000001], sumA[4], sumB[4], mx[4];
bool prv[4];

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

	int n; cin >> n;
	string A, B; cin >> A >> B;
	prv[1] = prv[3] = true;

	memset(dp, 0x3f3f3f3f, sizeof(dp));
	dp[0] = 0;

	for (int i = 1; i <= n; i++) {
		int& ret = dp[i];
		if (!prv[0] && B[i-1] == '1') sumA[0]++;
		if (prv[0] && B[i-1] == '0') sumB[0]++;
		ret = min(ret, mx[0]+sumA[0] + 1);
		prv[0] = B[i-1] == '1';

		if (prv[1] && B[i-1] == '0') sumA[1]++;
		if (!prv[1] && B[i-1] == '1') sumB[1]++;
		ret = min(ret, mx[1] + sumA[1] + 1);
		prv[1] = B[i-1] == '1';

		if (!prv[2] && A[i-1] == B[i-1]) sumA[2]++;
		if (prv[2] && A[i-1] != B[i-1]) sumB[2]++;
		ret = min(ret, mx[2] + sumA[2] + 1);
		prv[2] = A[i-1] == B[i-1];

		if (prv[3] && A[i-1] != B[i-1]) sumA[3]++;
		if (!prv[3] && A[i-1] == B[i-1]) sumB[3]++;
		ret = min(ret, mx[3] + sumA[3]);
		prv[3] = A[i-1] == B[i-1];

		for (int j = 0; j < 4; j++) mx[j] = min(mx[j], dp[i-1] - sumB[j]);
	}
	cout << dp[n];

	return 0;
}

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