This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "bits/stdc++.h"
using namespace std;
const int N=1e6;
int n;
string s, t;
int a[N], b[N];
int dp[N][3];
int main(){
cin.tie(0)->sync_with_stdio(0);
cin >> n >> s >> t;
for(int i=0; i<n; i++){
a[i]=s[i]=='1';
b[i]=t[i]=='1';
for(int j=0; j<3; j++) dp[i][j]=1e9;
}
dp[0][0]=1+b[0];
dp[0][1]=1+!b[0];
dp[0][2]=a[0]^b[0];
// for(int k=0; k<3; k++) cout << dp[0][k] << " ";
// cout << "\n";
for(int i=1; i<n; i++){
for(int j=0; j<3; j++){
for(int k=0; k<3; k++){
int old=(j<2?j:a[i-1]);
int val=(k<2?k:a[i]);
dp[i][k]=min(dp[i][k], dp[i-1][j]+(j!=1 && k==1) + (j!=0 && k==0) + ((val^b[i])&&(old==b[i-1])));
}
}
// for(int k=0; k<3; k++) cout << dp[i][k] << " ";
// cout << "\n";
}
cout << min({dp[n-1][0], dp[n-1][1], dp[n-1][2]});
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |