Submission #893919

#TimeUsernameProblemLanguageResultExecution timeMemory
893919boxLamps (JOI19_lamps)C++17
100 / 100
75 ms4776 KiB
#include <bits/stdc++.h>
using namespace std;

#define ar array
#define sz(v) int(std::size(v))
using i64 = long long;

const int INF = 1e9;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N;
    cin >> N;
    string A, B;
    cin >> A >> B;
    int dp[3][2], ndp[3][2];
    for (int x : {0,1,2}) for (int y : {0,1}) dp[x][y] = INF;
    dp[0][0] = 0;
    for (int i = 0; i < N; i++) {
        for (int x : {0,1,2}) for (int y : {0,1}) ndp[x][y] = INF;
        for (int x1 : {0,1,2}) for (int y1 : {0,1}) for (int x2 : {0,1,2}) for (int y2 : {0,1})
            ndp[x2][y2] = min(ndp[x2][y2], dp[x1][y1] + (x1 != x2 && x2 > 0) + (y2 > y1));
        for (int x : {0,1,2}) for (int y : {0,1}) {
            int v = (x ? x - 1 : A[i] - '0') ^ y;
            if (v != B[i] - '0') ndp[x][y] = INF;
        }
        swap(dp, ndp);
    }
    int ans = INF;
    for (int x : {0,1,2}) for (int y : {0,1}) ans = min(ans, dp[x][y]);
    cout << ans << '\n';
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...