Submission #1328218

#TimeUsernameProblemLanguageResultExecution timeMemory
1328218WH8Lamps (JOI19_lamps)C++17
4 / 100
112 ms63032 KiB
#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define int long long
#define pb push_back
#define f first
#define s second
#define ld long double
#define sz(x) static_cast<int>((x).size())
#define i5 tuple<int,int,int,int,int>
#define all(x) x.begin(), x.end()
#define iii tuple<int,int,int>
#define eb emplace_back
#define mt make_tuple
#define pll pair<int,int>
#define lol pair<int, vector<int>> 

int dp[1000005][3][2];

void chmin(int & x, int v){
	x = min(x, v);
}
signed main(){
	int n;cin>>n;
	vector<int> a(n+1, 0), b(n+1, 0);
	for(int i=1;i<=n;i++){
		char c;cin>>c;
		if(c=='1')a[i]=1;
	}
	for(int i=1;i<=n;i++){
		char c;cin>>c;
		if(c=='1')b[i]=1;
	}
	for(int i=0;i<=n;i++){
		for(int j=0;j<3;j++){
			for(int k=0;k<2;k++){
				dp[i][j][k]=1e15;
			}
		}
	}
	dp[0][2][0]=0;
	for (int i=1;i<=n;i++){
		int add=0;
		for(int j1=0;j1<2;j1++){
			for(int k=0;k<2;k++){
				for(int j2=0;j2<2;j2++){
					add=0;
					if(!k and j2 == 0 and j1 == 1) add++;
					if(k and j2 == 1 and j1 == 0) add++;
					if (j2 ^ b[i-1] == 0 and b[i] ^ j1 == 1) add++;
					chmin(dp[i][j1][k],dp[i-1][j2][k] + add);
				}
				if(j1 == k){ // start alternate block, must be equal
					add=1; // transition from 2, must +1 immediately
					if (b[i-1] ^ b[i-1] == 0 and b[i] ^ j1 == 1) add++;
					chmin(dp[i][j1][k], dp[i-1][2][0] + add);
				}
			}
		}
		// transition to 2 from 0/1 no normal add, xor add still need
		for(int j2=0;j2<2;j2++){
			for(int k2=0;k2<2;k2++){
				add=0;
				if(j2 ^ b[i-1] == 0 and a[i] ^ b[i] == 1) add++;
				chmin(dp[i][2][0], dp[i-1][j2][k2]+add);
			}
		}
		// transitionf rom 2 to 2.
		add=0;
		if(a[i-1] ^ b[i-1] == 0 and a[i] ^ b[i] == 1) add++;
		chmin(dp[i][2][0], dp[i-1][2][0] + add);
	}
	int ans=1e15;
	for(int j=0;j<3;j++){
		for(int k=0;k<2;k++){
			chmin(ans, dp[n][j][k]);
		}
	}
	/*for(int i=0;i<3;i++){
		for(int j=0;j<2;j++){
			cout<<dp[3][i][j]<<" ";
		}
		cout<<endl;
	}*/
	assert(ans < 1e9);
	cout<<ans;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...