Submission #1352668

#TimeUsernameProblemLanguageResultExecution timeMemory
1352668rmielamudLamps (JOI19_lamps)C++20
100 / 100
28 ms25852 KiB
#include <bits/stdc++.h>

using namespace std;

#define short int32_t
#define int int64_t
#define long __int128_t

const int inf{numeric_limits<int>::max() / 4};

short main() {
    #ifndef LOCAL
        ios_base::sync_with_stdio(false);
        cin.tie(nullptr);
    #endif

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

    a = "0" + a;
    b = "0" + b;

    vector<array<int, 3>> dp(n + 1);
    
    for (int i{0}; i <= n; i++) {
        for (int j{0}; j < 3; j++) {
            dp[i][j] = inf;
        }
    }

    dp[0][2] = 0;

    for (int i{1}; i <= n; i++) {
        for (int j{0}; j < 3; j++) {
            for (int j2{0}; j2 < 3; j2++) {
                int prev_char{j2 == 2 ? a[i - 1] - '0' : j2};
                bool prev_correct{prev_char == b[i - 1] - '0'};
                int curr_char{j == 2 ? a[i] - '0' : j};
                bool curr_correct{curr_char == b[i] - '0'};

                dp[i][j] = min(
                    dp[i][j],
                    dp[i - 1][j2] + (j != j2 && j != 2) + (prev_correct && !curr_correct)
                );
            }
        }
    }

    cout << min({dp[n][0], dp[n][1], dp[n][2]}) << "\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...