Submission #124572

#	Time	Username	Problem	Language	Result	Execution time	Memory
124572		vex	Lamps (JOI19_lamps)	C++14	4 / 100	27 ms	20128 KiB

lamp

#include <bits/stdc++.h>
#define maxn   1000005
#define INF 1000020000
using namespace std;

int n;
string a,b;
int dp[maxn][2][2];

int minn(int x)
{
	return min(min(dp[x][0][0],dp[x][0][1]), min(dp[x][1][0],dp[x][1][1]));
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	
	cin>>n;
	cin>>a;
	cin>>b;
	
	if(a[0]==b[0])
	{
		dp[0][0][0]=0;
		dp[0][0][1]=INF;
		dp[0][1][0]=1;
		dp[0][1][1]=2;
	}
	else
	{
		dp[0][0][0]=INF;
		dp[0][0][1]=1;
		dp[0][1][0]=1;
		dp[0][1][1]=2;
	}
	
	for(int i=1;i<n;i++)
	{
		if(a[i]==b[i])
		{
			dp[i][0][0]=minn(i-1);
			dp[i][0][1]=INF;
			
			dp[i][1][0]=minn(i-1)+1;
			if(b[i-1]==b[i])dp[i][1][0]=min(dp[i][1][0],dp[i-1][1][0]);
			else dp[i][1][0]=min(dp[i][1][0],dp[i-1][1][1]);
			
			dp[i][1][1]=minn(i-1)+2;
			if(b[i]==b[i-1])dp[i][1][1]=min(dp[i][1][1],dp[i-1][1][1]);
			if(b[i-1]+b[i]==1)dp[i][1][1]=min(dp[i][1][1],dp[i-1][1][0]+1);
			dp[i][1][1]=min( min(dp[i-1][0][1],dp[i-1][1][1])+1, dp[i][1][1]);
		}
		else
		{
			dp[i][0][0]=INF;
			
			dp[i][0][1]=min( min(dp[i-1][0][1],dp[i-1][1][1]), min(dp[i-1][0][0],dp[i-1][1][0])+1 );
			
			dp[i][1][0]=minn(i-1)+1;
			if(b[i-1]==b[i])dp[i][1][0]=min(dp[i][1][0],dp[i-1][1][0]);
			else dp[i][1][0]=min(dp[i][1][0],dp[i-1][1][1]);
			
			dp[i][1][1]=minn(i-1)+2;
			if(b[i]==b[i-1])dp[i][1][1]=min(dp[i][1][1],dp[i-1][1][1]);
			if(b[i-1]+b[i]==1)dp[i][1][1]=min(dp[i][1][1],dp[i-1][1][0]+1);
			dp[i][1][1]=min( min(dp[i-1][0][1],dp[i-1][1][1])+1, dp[i][1][1]);
		}
	}
	
	/*for(int i=0;i<n;i++)
	{
		cout<<i<<": "<<dp[i][0][0]<<" "<<dp[i][0][1]<<" "<<dp[i][1][0]<<" "<<dp[i][1][1]<<endl;
	}*/
	
	cout<<minn(n-1)<<endl;
	return 0;
}

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