Submission #332655

#TimeUsernameProblemLanguageResultExecution timeMemory
332655LawlietLamps (JOI19_lamps)C++17
4 / 100
85 ms33760 KiB
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1000010;

int n;

int dp[MAXN][6];
int A[MAXN], B[MAXN];

string a, b;

int main()
{
	cin >> n >> a >> b;

	for(int i = 1 ; i <= n ; i++)
	{
		A[i] = a[i - 1] - '0';
		B[i] = b[i - 1] - '0';
	}

	dp[0][4] = 1;
	dp[0][0] = dp[0][1] = 1;
	dp[0][2] = dp[0][3] = 2;

	for(int i = 1 ; i <= n ; i++)
	{
		for(int k = 0 ; k < 4 ; k++)
		{
			int s = 0;
			if( k == 1 || k == 2 ) s = 1; 

			if( B[i] == s ) dp[i][k] = min( dp[i - 1][k] , dp[i - 1][3 - k] + 3 );
			else dp[i][k] = min( dp[i - 1][k^2] + 1 , dp[i - 1][k^1] + 2 );
		}

		if( A[i] == B[i] ) dp[i][4] = min( dp[i - 1][5] + 1 , dp[i - 1][1 - B[i] + 2] + 1 );
		else dp[i][4] = min( dp[i - 1][4] , dp[i - 1][ A[i] ] + 2 );

		if( A[i] == B[i] ) dp[i][5] = min( dp[i - 1][5] , dp[i - 1][ 1 - B[i] + 2 ] + 2 );
		else dp[i][5] = min( dp[i - 1][4] + 1 , dp[i - 1][ B[i] ] + 1 );
	}

	printf("%d\n",dp[n][5]/2);
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...