Submission #157040

#	Time	Username	Problem	Language	Result	Execution time	Memory
157040		HungAnhGoldIBO2020	Lamps (JOI19_lamps)	C++14	100 / 100	108 ms	63132 KiB

lamp

#include<iostream>
using namespace std;
const int N=1e6+2;
const int inf=1e9+7;
int dp[N][5][3];
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n,i,j,k,l,m,z;
	string a,b;
	cin>>n>>a>>b;
	a=" "+a;
	b=" "+b;
	for(j=0;j<3;j++){
		for(k=0;k<2;k++){
			dp[0][j][k]=inf;
		}
	}
	dp[0][0][0]=0;
	for(i=1;i<=n;i++){
		for(j=0;j<3;j++){
			for(k=0;k<2;k++){
				dp[i][j][k]=inf;
				if(j>0){
					z=j-1;
				}
				else{
					z=(int)(a[i]-'0');
				}
				if(k){
					z=1-z;
				}
				if(z!=(int)(b[i]-'0')){
					continue;
				}
				for(l=0;l<3;l++){
					for(m=0;m<2;m++){
						z=0;
						if(j>0&&j!=l){
							z++;
						}
						if(k==1&&m==0){
							z++;
						}
						dp[i][j][k]=min(dp[i][j][k],dp[i-1][l][m]+z);
					}
				}
		//		cout<<dp[i][j][k]<<' '<<i<<' '<<j<<' '<<k<<endl;
			}
		}
	}
	for(j=0;j<3;j++){
		for(k=0;k<2;k++){
			dp[n][0][0]=min(dp[n][0][0],dp[n][j][k]);
		}
	}
	cout<<dp[n][0][0];
}

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