Submission #1185784

#TimeUsernameProblemLanguageResultExecution timeMemory
1185784irmuunLamps (JOI19_lamps)C++20
100 / 100
35 ms22024 KiB
#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define pb push_back
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
#define rall(s) s.rbegin(),s.rend()

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int n;
    cin>>n;
    string s,t;
    cin>>s>>t;
    int a[n+5],b[n+5];
    for(int i=1;i<=n;i++){
        a[i]=(s[i-1]-'0');
        b[i]=(t[i-1]-'0');
    }
    int dp[n+5][3];
    dp[0][0]=0;
    dp[0][1]=dp[0][2]=1e9;
    //dp[i][j]=x+y, x-set range, y-flip range
    for(int i=1;i<=n;i++){
        for(int j=0;j<3;j++) dp[i][j]=1e9;
        for(int j=0;j<3;j++){
            for(int k=0;k<3;k++){
                int bef=0;//1-same,0-dif
                int now=0;
                if(i==1) bef=1;
                else{
                    if(j==0) bef=(a[i-1]==b[i-1]?1:0);
                    else if(j==1) bef=(b[i-1]==0?1:0);
                    else bef=(b[i-1]==1?1:0);
                }
                if(k==0) now=(a[i]==b[i]?1:0);
                else if(k==1) now=(b[i]==0?1:0);
                else now=(b[i]==1?1:0);
                dp[i][k]=min(dp[i][k],dp[i-1][j]+(k!=0&&k!=j)+(bef==1&&now==0));
            }
        }
    }
    cout<<min({dp[n][0],dp[n][1],dp[n][2]});
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...