Submission #755154

#TimeUsernameProblemLanguageResultExecution timeMemory
755154Dan4LifeLamps (JOI19_lamps)C++17
47 / 100
9 ms7884 KiB
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define lb lower_bound
#define all(a) begin(a),end(a)

const int mxN = (int)2e5+10;

string s, ss;
int n, a[mxN], b[mxN], dp[mxN][3];

int main(){
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> n >> s >> ss; int ans = mxN;
	for(int i = 0; i < n; i++) 
		a[i+1] = s[i]=='1', b[i+1] = ss[i]=='1';
	memset(dp,63,sizeof(dp)); dp[0][2] = 0;
	for(int i = 1; i <= n; i++){
		for(int j = 0; j < 3; j++){
			bool eq = ((j==2 and a[i]==b[i]) or j==b[i]);
			dp[i][j] = min(dp[i][j], dp[i-1][0]+!b[i-1]*!eq+(j==1));
			dp[i][j] = min(dp[i][j], dp[i-1][1]+b[i-1]*!eq+(j==0));
			dp[i][j] = min(dp[i][j], dp[i-1][2]+!eq*(a[i-1]==b[i-1])+(j!=2));
			if(i==n) ans = min(ans, dp[i][j]);
		}
	}
	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...