Submission #1276754

#TimeUsernameProblemLanguageResultExecution timeMemory
1276754duckindogLamps (JOI19_lamps)C++20
100 / 100
46 ms20004 KiB
#include <bits/stdc++.h>

using namespace std;

const int N = 1'000'000 + 10;
int n;
int a[N], b[N];

const int MAX = 1'000'000'000;
int f[N][3];

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

    cin >> n;
    for (int i = 1; i <= n; ++i) { 
        char ch; cin >> ch;
        a[i] = (ch == '1');
    }
    for (int i = 1; i <= n; ++i) { 
        char ch; cin >> ch;
        b[i] = (ch == '1');
    }

    auto useXor = [&](int i, int j) { 
        return !j ? a[i] != b[i] : (j - 1 != b[i]);
    };

    memset(f, 63, sizeof f);

    f[1][0] = useXor(1, 0);
    f[1][1] = 1 + useXor(1, 1);
    f[1][2] = 1 + useXor(1, 2);
    for (int i = 2; i <= n; ++i) { 
        { // f[i][0] no assign line
            auto& ret = f[i][0];
            for (int j = 0; j <= 2; ++j) { 
                ret = min(ret, f[i - 1][j] + (useXor(i, 0) && !useXor(i - 1, j)));
            }
        }

        { // f[i][1] assign line is 0
            auto& ret = f[i][1];
            for (int j = 0; j <= 2; ++j) { 
                ret = min(ret, f[i - 1][j] + (j != 1) + (useXor(i, 1) && !useXor(i - 1, j)));
            }
        }

        { // f[i][1] assign line is 1
            auto& ret = f[i][2];
            for (int j = 0; j <= 2; ++j) { 
                ret = min(ret, f[i - 1][j] + (j != 2) + (useXor(i, 2) && !useXor(i - 1, j)));
            }
        }
    }
    
    cout << min({f[n][0], f[n][1], f[n][2]}) << "\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...