Submission #332655

#	Time	Username	Problem	Language	Result	Execution time	Memory
332655		Lawliet	Lamps (JOI19_lamps)	C++17	4 / 100	85 ms	33760 KiB

lamp

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

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