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;
#define REP(i,j,k) for(int i=(j);i<(k);++i)
#define MIN(x,y) (x=min(x,(y)))
const int maxn=1e6+9,inf=1e9;
int n,dp[maxn][2][3];
string a,b;
main(){
cin>>n>>a>>b;
a+='0',b+='0',++n;
REP(i,0,n+1)REP(j,0,2)REP(k,0,3)dp[i][j][k]=inf;
dp[0][0][2]=0;
REP(i,0,n)REP(j,0,2)REP(k,0,2){
MIN(dp[i+1][k][0],dp[i][j][2]+(!j&&k)+1);
if(i)REP(l,0,2)REP(m,0,2){
if(b[i-1]-'0'^j^b[i]-'0'^k^l^m^1)MIN(dp[i+1][k][l],dp[i][j][m]+(!j&&k)+(l==1&&m==0));
}
if(a[i]-'0'^b[i]-'0'^k^1)REP(l,0,3)MIN(dp[i+1][k][2],dp[i][j][l]+(!j&&k));
}
cout<<dp[n][0][2]<<endl;
}
Compilation message (stderr)
lamp.cpp:10:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
main(){
^
lamp.cpp: In function 'int main()':
lamp.cpp:18:13: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
if(b[i-1]-'0'^j^b[i]-'0'^k^l^m^1)MIN(dp[i+1][k][l],dp[i][j][m]+(!j&&k)+(l==1&&m==0));
lamp.cpp:18:24: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
if(b[i-1]-'0'^j^b[i]-'0'^k^l^m^1)MIN(dp[i+1][k][l],dp[i][j][m]+(!j&&k)+(l==1&&m==0));
lamp.cpp:20:10: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
if(a[i]-'0'^b[i]-'0'^k^1)REP(l,0,3)MIN(dp[i+1][k][2],dp[i][j][l]+(!j&&k));
# | 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... |