제출 #941448

#제출 시각아이디문제언어결과실행 시간메모리
941448juliany2Lamps (JOI19_lamps)C++17
100 / 100
39 ms4768 KiB
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(x) (x).begin(), (x).end()

void ckmin(int &x, int y) {
    x = min(x, y);
}

int main() {
    cin.tie(0)->sync_with_stdio(false);

    int n;
    string a, b;
    cin >> n >> a >> b;

    vector<vector<int>> dp(2, vector<int> (3, 1e9));
    dp[0][0] = 0;

    for (int i = 0; i < n; i++) {
        for (int x : {0, 1})
            for (int y : {0, 1, 2})
                ckmin(dp[x][0], dp[x][y]);

        for (int y : {0, 1, 2})
            ckmin(dp[0][y], dp[1][y]);

        for (int x : {0, 1})
            for (int y : {1, 2})
                ckmin(dp[x][y], dp[x][0] + 1);

        for (int y : {0, 1, 2})
            ckmin(dp[1][y], dp[0][y] + 1);

        for (int x : {0, 1}) {
            for (int y : {0, 1, 2}) {
                char have = (y == 0 ? a[i] : (y - 1 + '0'));
                if ((have == b[i]) == x)
                    dp[x][y] = 1e9;
            }
        }
    }

    int ans = 1e9;
    for (int x : {0, 1})
        for (int y : {0, 1, 2})
            ans = min(ans, dp[x][y]);

    cout << ans << '\n';

    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...