제출 #235735

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
235735		Charis02	Lamps (JOI19_lamps)	C++14	100 / 100	47 ms	27988 KiB

lamp

#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;
}

• Subtask 1: 6 / 6
• Subtask 2: 41 / 41
• Subtask 3: 4 / 4
• Subtask 4: 49 / 49