Submission #384431

#	Time	Username	Problem	Language	Result	Execution time	Memory
384431		ogibogi2004	Lamps (JOI19_lamps)	C++14	4 / 100	190 ms	39680 KiB

lamp

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e6+6;
int dp[MAXN][2][2][2];
int a[MAXN],b[MAXN];
int main()
{
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		char c;
		cin>>c;
		a[i]=c-'0';
	}
	for(int i=1;i<=n;i++)
	{
		char c;
		cin>>c;
		b[i]=c-'0';
	}
	for(int i=0;i<MAXN;i++)
	{
		for(int i1=0;i1<2;i1++)
		for(int i2=0;i2<2;i2++)
		for(int i3=0;i3<2;i3++)
		dp[i][i1][i2][i3]=MAXN+3;
	}
	dp[0][0][0][0]=0;
	for(int i=1;i<=n;i++)
	{
		for(int i1=0;i1<2;i1++)
		for(int i2=0;i2<2;i2++)
		for(int i3=0;i3<2;i3++)
		{
			if(i2&&i3)continue;
			int a1=a[i];
			if(i1)a1=1-a1;
			if(i2)a1=0;
			if(i3)a1=1;
			if(a1==b[i])
			{
				for(int j1=0;j1<2;j1++)
				for(int j2=0;j2<2;j2++)
				for(int j3=0;j3<2;j3++)
				{
					dp[i][i1][i2][i3]=min(dp[i][i1][i2][i3],dp[i-1][j1][j2][j3]+(i1==1&&j1==0)+(i2==1&&j2==0)+(i3==1&&j3==0));
				}
			}
		}
		/*cout<<i<<":\n";
		for(int i1=0;i1<2;i1++)
		for(int i2=0;i2<2;i2++)
		for(int i3=0;i3<2;i3++)
		{
			cout<<i1<<" "<<i2<<" "<<i3<<" "<<dp[i][i1][i2][i3]<<endl;
		}*/
	}
	int ans=MAXN;
	for(int i1=0;i1<2;i1++)
	for(int i2=0;i2<2;i2++)
	for(int i3=0;i3<2;i3++)
	{
		ans=min(ans,dp[n][i1][i2][i3]);
	}
	cout<<ans<<endl;
return 0;
}

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