Submission #636616

#	Time	Username	Problem	Language	Result	Execution time	Memory
636616		aebov	Lamps (JOI19_lamps)	C++17	100 / 100	90 ms	24016 KiB

lamp

#include<iostream>
using namespace std;
const int N=(int)1e6+5;

int n;
string s, t;
int A[N],B[N], dp[N][3] , co[3][3]={{0,1,1},{1,0,2},{1,2,0}};

int main()
{
	cin >> n >> s >> t;
	for(int i=1;i<=n;i++)A[i]=s[i-1]-'0';
	for(int i=1;i<=n;i++)B[i]=t[i-1]-'0';
	n++;
	A[n]=B[n]=0;
	dp[1][0]=A[1]^B[1];
	dp[1][1]=(0^B[1])+1;
	dp[1][2]=(1^B[1])+1;
	for(int i=2;i<=n;i++)for(int j=0;j<3;j++)dp[i][j]=2*N;
	for(int i=2;i<=n;i++){
		for(int j=0;j<3;j++){
			for(int k=0;k<3;k++)
			{
				int x,y,prv,nxt;
				x=(j%2==1)?0:((j&2)? 1 : A[i-1]);
				y=(k%2==1)?0:((k&2)? 1 : A[i]);
				prv=x^B[i-1];
				nxt=y^B[i];
				dp[i][k]=min(dp[i][k],dp[i-1][j]+co[j][k]+(prv^nxt));
			}
		}
	}	
	//int ret = min ( dp[n][0], min (dp[n][1] , dp[n][2]));
	cout << dp[n][0] / 2  << endl;
}

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