Submission #126422

#	Time	Username	Problem	Language	Result	Execution time	Memory
126422		TadijaSebez	Lamps (JOI19_lamps)	C++11	10 / 100	83 ms	61080 KiB

lamp

#include <bits/stdc++.h>
using namespace std;
const int N=1000050;
const int inf=1e9+7;
int col[N][3][2][2];
int dp[N][3];
char a[N],b[N];
int main()
{
	int n;
	scanf("%i %s %s",&n,a+1,b+1);
	dp[0][0]=0;dp[0][1]=dp[0][2]=inf;
	for(int i=0;i<3;i++) for(int j=0;j<2;j++) for(int k=0;k<2;k++) col[0][i][j][k]=inf;
	for(int t=1;t<=n;t++)
	{
		for(int i=0;i<3;i++)
			for(int k=0;k<2;k++)
			{
				col[t][i][0][k]=inf;
				if(b[t]!=b[t-1])
				{
					if(i<3) col[t][i][1][k]=min(col[t-1][i][1][k^1]+(k==0),col[t-1][i][0][k^1]+(k==0));
					else col[t][i][1][k]=min(col[t-1][i][1][k^1]+(k==1),col[t-1][i][0][k^1]+(k==1));
				}
				else col[t][i][1][k]=col[t-1][i][1][k],col[t][i][0][k]=col[t-1][i][0][k];
			}
		col[t][0][0][1]=min(col[t][0][0][1],dp[t-1][0]+1);
		col[t][1][0][1]=min(col[t][1][0][1],dp[t-1][1]+1);
		col[t][1][0][1]=min(col[t][1][0][1],dp[t-1][2]+1);
		col[t][2][0][1]=min(col[t][2][0][1],dp[t-1][2]+1);
		col[t][2][0][1]=min(col[t][2][0][1],dp[t-1][1]+1);
		int A=inf,B=inf,C=inf;
		for(int j=0;j<2;j++) for(int k=0;k<2;k++)
		{
			A=min(A,col[t-1][0][j][k]);
			B=min(B,col[t-1][1][j][k]);
			C=min(C,col[t-1][2][j][k]);
		}
		if(a[t]!=b[t])
		{
			dp[t][0]=inf;
			dp[t][1]=min(A+1,min(B,C+1));
			dp[t][1]=min(dp[t][1],dp[t-1][0]+1);
			dp[t][1]=min(dp[t][1],dp[t-1][1]);
			dp[t][2]=min(col[t-1][0][1][0],min(col[t-1][1][1][0],col[t-1][2][1][1]));
			dp[t][2]=min(dp[t][2],dp[t-1][2]);
		}
		else
		{
			dp[t][0]=min(min(dp[t-1][0],min(dp[t-1][1],dp[t-1][2])),min(A,min(B,C)));
			dp[t][1]=inf;
			dp[t][2]=inf;
		}
	}
	int ans=min(dp[n][0],min(dp[n][1],dp[n][2]));
	for(int i=0;i<3;i++) for(int j=0;j<2;j++) for(int k=0;k<2;k++) ans=min(ans,col[n][i][j][k]);
	printf("%i\n",ans);
	return 0;
}

Compilation message (stderr)

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

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