Submission #235735

#TimeUsernameProblemLanguageResultExecution timeMemory
235735Charis02Lamps (JOI19_lamps)C++14
100 / 100
47 ms27988 KiB
#include<iostream>
#include<stdio.h>
#include<vector>
#include<cmath>
#include<queue>
#include<string.h>
#include<unordered_map>
#include<set>
#include<algorithm>
#define ll int
#define pi pair < ll,ll >
#define mp(a,b) make_pair(a,b)
#define mid (low+high)/2
#define rep(i,a,b) for(int i = a;i < b;i++)
#define N 1000004
#define INF 1000004

using namespace std;

ll n;
string s,t;
int dp[N][6];

/* 0: den ekana operation sto i, 1: kame to i set se 1, 2: kame to i set se 0,
3:kame to i toggle, 4: kame to i 1 kai meta toggle, 5: kame to i 0 kai meta toggle
*/

void solve()
{
    if(s[0]==t[0])
    {
        dp[0][0] = 0;
        dp[0][3] = INF;
    }
    else
    {
        dp[0][0] = INF;
        dp[0][3] = 1;
    }


    if(t[0] == '0')
    {
        dp[0][2] = 1;
        dp[0][1] = INF;

        dp[0][4] = 2;
        dp[0][5] = INF;
    }
    else
    {
        dp[0][1] = 1;
        dp[0][2] = INF;

        dp[0][4] = INF;
        dp[0][5] = 2;
    }

    rep(i,1,n)
    {
        if(s[i] == t[i])
        {
            dp[i][0] = min(dp[i-1][0],dp[i-1][1]);
            dp[i][0] = min(dp[i][0],dp[i-1][2]);
            dp[i][0] = min(dp[i][0],dp[i-1][3]);
            dp[i][0] = min(dp[i][0],dp[i-1][4]);
            dp[i][0] = min(dp[i][0],dp[i-1][5]);

            dp[i][3] = INF;
        }
        else
        {
            dp[i][0] = INF;

            dp[i][3] = min(dp[i-1][0]+1,dp[i-1][1]+1);
            dp[i][3] = min(dp[i][3],dp[i-1][2]+1);
            dp[i][3] = min(dp[i][3],dp[i-1][3]);
            dp[i][3] = min(dp[i][3],dp[i-1][4]);
            dp[i][3] = min(dp[i][3],dp[i-1][5]);
        }

        if(t[i] == '1')
        {
            dp[i][2] = INF;

            dp[i][1] = min(dp[i-1][0]+1,dp[i-1][1]);
            dp[i][1] = min(dp[i][1],dp[i-1][2]+1);
            dp[i][1] = min(dp[i][1],dp[i-1][3]+1);
            dp[i][1] = min(dp[i][1],dp[i-1][4]);
            dp[i][1] = min(dp[i][1],dp[i-1][5]+1);

            dp[i][4] = INF;

            dp[i][5] = min(dp[i-1][0]+2,dp[i-1][1]+2);
            dp[i][5] = min(dp[i][5],dp[i-1][2]+1);
            dp[i][5] = min(dp[i][5],dp[i-1][3]+1);
            dp[i][5] = min(dp[i][5],dp[i-1][4]+1);
            dp[i][5] = min(dp[i][5],dp[i-1][5]);
        }
        else
        {
            dp[i][1] = INF;

            dp[i][2] = min(dp[i-1][0]+1,dp[i-1][2]);
            dp[i][2] = min(dp[i][2],dp[i-1][1]+1);
            dp[i][2] = min(dp[i][2],dp[i-1][3]+1);
            dp[i][2] = min(dp[i][2],dp[i-1][4]+1);
            dp[i][2] = min(dp[i][2],dp[i-1][5]);

            dp[i][5] = INF;

            dp[i][4] = min(dp[i-1][0]+2,dp[i-1][2]+2);
            dp[i][4] = min(dp[i][4],dp[i-1][1]+1);
            dp[i][4] = min(dp[i][4],dp[i-1][3]+1);
            dp[i][4] = min(dp[i][4],dp[i-1][4]);
            dp[i][4] = min(dp[i][4],dp[i-1][5]+1);
        }
    }

    return;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;
    cin >> s;
    cin >> t;

    solve();
    cout << min({dp[n-1][0],dp[n-1][1],dp[n-1][2],dp[n-1][3],dp[n-1][4],dp[n-1][5]});

    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...