Submission #251939

#	Time	Username	Problem	Language	Result	Execution time	Memory
251939		nnnnnnnnnnnnnnnn	Lamps (JOI19_lamps)	C++14	4 / 100	129 ms	20076 KiB

lamp

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef vector<int> vi;
typedef pair<int,int> ii;
typedef pair<ll,int> pli;
typedef pair<int,ll> pil;
typedef pair<ll,ll> pll;
const int N = 1e6,inf = 1e8;
int n;
string a,b;
int dp[4][N];	
// ->0
// ->1
// flip
int solve()
{
	int i,j,k;
	for(i=0;i<4;i++)
	{
		for(j=0;j<n;j++)
		{
			dp[i][j] = inf;
		}
	}
	if(a[0]==b[0])
	{
		if(a[0]=='0')	dp[0][0] = 1;
		else			dp[1][0] = 1;
		dp[3][0] = 0;
	}
	else
	{
		dp[2][0] = 1;
		if(b[0]=='0')	dp[0][0] = 1;
		else			dp[1][0] = 1;
	}
	for(i=1;i<n;i++)
	{
		for(j=0;j<4;j++)
		{
			for(k=0;k<4;k++)
			{
				dp[j][i] = min(dp[j][i],dp[k][i-1]+1);
			}
		}
		if(a[i]==b[i])
		{
			for(j=0;j<4;j++)
			{
				dp[3][i] = min(dp[3][i],dp[j][i-1]);
			}
			if(a[i]=='0')
			{
				dp[0][i] = min(dp[0][i],dp[0][i-1]);
	//			dp[3][i] = min(dp[3][i],dp[3][i-1]);
			}
			else
			{
				dp[1][i] = min(dp[1][i],dp[1][i-1]);
	//			dp[3][i] = min(dp[3][i],dp[3][i-1]);
			}
		}
		else
		{
			if(a[i]=='0')
			{
				dp[2][i] = min(dp[2][i],dp[2][i-1]);
				dp[1][i] = min(dp[1][i],dp[1][i-1]);
			}
			else
			{
				dp[2][i] = min(dp[2][i],dp[2][i-1]);
				dp[0][i] = min(dp[0][i],dp[0][i-1]);
			}
		}
	}
/*	for(i=0;i<4;i++)
	{
		for(j=0;j<n;j++)
		{
			if(dp[i][j]==inf)	printf("! ");
			else
			printf("%d ",dp[i][j]);
		}
		printf("\n");
	}			*/
	int ans = min(min(dp[0][n-1],dp[1][n-1]),min(dp[2][n-1],dp[3][n-1]));
	return ans;
}
int main()
{
	scanf("%d",&n);
	cin >> a >> b;
	int res = solve();
	printf("%d",res);
}

Compilation message (stderr)

lamp.cpp: In function 'int main()':
lamp.cpp:93:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
  ~~~~~^~~~~~~~~

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