제출 #1317666

#제출 시각아이디문제언어결과실행 시간메모리
1317666boclobanchatLamps (JOI19_lamps)C++20
100 / 100
32 ms27944 KiB
#include<bits/stdc++.h> using namespace std; const int MAXN=1e6+5; const int INF=1e9; int dp[MAXN][2][3]; int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n; string a,b; cin>>n>>a>>b; for(int i=0;i<=n;i++) for(int j=0;j<2;j++) dp[i][j][0]=dp[i][j][1]=dp[i][j][2]=INF; dp[0][0][0]=0,a='0'+a,b='0'+b; for(int i=1;i<=n;i++) for(int j=0;j<2;j++) { if(a[i]-'0'==j) for(int k=0;k<2;k++) { bool z=(b[i-1]-'0'!=k)^(b[i]-'0'!=j); dp[i][j][0]=min(dp[i][j][0],dp[i-1][k][0]+z); dp[i][j][0]=min(dp[i][j][0],dp[i-1][k][1]+z+1); dp[i][j][0]=min(dp[i][j][0],dp[i-1][k][2]+z+1); } for(int k=0;k<2;k++) { bool z=(b[i-1]-'0'!=k)^(b[i]-'0'!=j); dp[i][j][j+1]=min(dp[i][j][j+1],dp[i-1][k][0]+z+1); dp[i][j][j+1]=min(dp[i][j][j+1],dp[i-1][k][1]+z+(j!=0)*2); dp[i][j][j+1]=min(dp[i][j][j+1],dp[i-1][k][2]+z+(j!=1)*2); } } int ans=1e9; for(int k=0;k<2;k++) ans=min(ans,min(dp[n][0][k]+(b[n]!='0')+(k>0),dp[n][1][k]+(b[n]!='1')+(k>0))/2); 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...