Submission #755097

#TimeUsernameProblemLanguageResultExecution timeMemory
755097Dan4LifeLamps (JOI19_lamps)C++17
0 / 100
11 ms7832 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];

int main(){
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> n >> s >> ss;
	for(int i = 0; i < n; i++) 
		a[i+1] = s[i]=='1', b[i+1] = ss[i]=='1';
	for(int i = 1; i <= n; i++){
		bool z=1, o=1, x=1, y = 1; dp[i]=i;
		for(int j = i; j>=1; j--){
			z&=!b[j], o&=b[j], x&=a[j]^b[j], y&=a[j]^!b[j];
			if(z or o or x) dp[i] = min(dp[i], dp[j-1]+1);
			if(y) dp[i] = min(dp[i], dp[j-1]);
		}
	}
	int ans = dp[n];
	for(int i = 1; i <= n; i++) a[i]^=1;
	for(int i = 1; i <= n; i++){
		bool z=1, o=1, x=1, y = 1; dp[i]=i;
		for(int j = i; j>=1; j--){
			z&=!b[j], o&=b[j], x&=a[j]^b[j], y&=a[j]^!b[j];
			if(z or o or x) dp[i] = min(dp[i], dp[j-1]+1);
			if(y) dp[i] = min(dp[i], dp[j-1]);
		}
	}
	cout << min(dp[n]+1,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...