Submission #917322

#	Time	Username	Problem	Language	Result	Execution time	Memory
917322		amirhoseinfar1385	Lamps (JOI19_lamps)	C++17	4 / 100	35 ms	27816 KiB

lamp

#include<bits/stdc++.h>
using namespace std;
const int maxn=1000000+10;
int dp[maxn][2][3],inf=maxn+10;

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n;
	string s,ss;
	cin>>n>>s>>ss;
	for(int i=0;i<2;i++){
		for(int j=0;j<3;j++){
			dp[0][i][j]=inf;
		}
	}
	dp[0][0][2]=0;
	for(int ind=1;ind<=n;ind++){
		for(int i=0;i<2;i++){
			for(int j=0;j<2;j++){
				dp[ind][i][j]=min(dp[ind-1][i^1][j]+(i==1),min(dp[ind-1][i^1][j^1]+(i==1),dp[ind-1][i^1][2]+(i==1))+1);
				dp[ind][i][j]=min(dp[ind-1][i][j],min(dp[ind-1][i][j^1],dp[ind-1][i][2])+1);	
			}
			dp[ind][i][2]=min(dp[ind-1][i][0],min(dp[ind-1][i][1],dp[ind-1][i][2]));
			dp[ind][i][2]=min(dp[ind][i][2],min(dp[ind-1][i^1][0],min(dp[ind-1][i^1][1],dp[ind-1][i^1][2]))+(i==1));
		}
		if(s[ind-1]==ss[ind-1]){
			dp[ind][0][(s[ind-1]-'0')^1]=inf;
			dp[ind][1][(s[ind-1]-'0')]=inf;
			dp[ind][1][2]=inf;
		}
		else{
			dp[ind][0][(s[ind-1]-'0')]=inf;
			dp[ind][0][2]=inf;
			dp[ind][1][(s[ind-1]-'0')^1]=inf;
		}
//		cout<<"injy: "<<ind<<"\n";
//		for(int i=0;i<2;i++){
//			for(int j=0;j<3;j++){
//				cout<<dp[ind][i][j]<<" ";
//			}
//			cout<<"\n";
//		}
//		cout<<"\n";
	}
	long long res=min(dp[n][0][0],min(dp[n][0][1],min(dp[n][0][2],min(dp[n][1][0],min(dp[n][1][1],dp[n][1][2])))));
	cout<<res<<"\n";
}

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