Submission #1317666

#	Time	Username	Problem	Language	Result	Execution time	Memory
1317666		boclobanchat	Lamps (JOI19_lamps)	C++20	100 / 100	32 ms	27944 KiB

lamp

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e6+5;
const int INF=1e9;
int dp[MAXN][2][3];
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n;
	string a,b;
	cin>>n>>a>>b;
	for(int i=0;i<=n;i++) for(int j=0;j<2;j++) dp[i][j][0]=dp[i][j][1]=dp[i][j][2]=INF;
	dp[0][0][0]=0,a='0'+a,b='0'+b;
	for(int i=1;i<=n;i++) for(int j=0;j<2;j++)
	{
		if(a[i]-'0'==j) for(int k=0;k<2;k++)
		{
			bool z=(b[i-1]-'0'!=k)^(b[i]-'0'!=j);
			dp[i][j][0]=min(dp[i][j][0],dp[i-1][k][0]+z);
			dp[i][j][0]=min(dp[i][j][0],dp[i-1][k][1]+z+1);
			dp[i][j][0]=min(dp[i][j][0],dp[i-1][k][2]+z+1);
		}
		for(int k=0;k<2;k++)
		{
			bool z=(b[i-1]-'0'!=k)^(b[i]-'0'!=j);
			dp[i][j][j+1]=min(dp[i][j][j+1],dp[i-1][k][0]+z+1);
			dp[i][j][j+1]=min(dp[i][j][j+1],dp[i-1][k][1]+z+(j!=0)*2);
			dp[i][j][j+1]=min(dp[i][j][j+1],dp[i-1][k][2]+z+(j!=1)*2);
		}
	}
	int ans=1e9;
	for(int k=0;k<2;k++) ans=min(ans,min(dp[n][0][k]+(b[n]!='0')+(k>0),dp[n][1][k]+(b[n]!='1')+(k>0))/2);
	cout<<ans;
}

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