CF991D AC

// Problem: D. Bishwock
// Contest: Codeforces - Codeforces Round 491 (Div. 2)
// URL: https://codeforces.com/contest/991/problem/D
// Memory Limit: 256 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)

#include <assert.h>
#include <bits/stdc++.h>
using namespace std;
#ifndef __DEBUG__
#define dbg(...) 42
#endif
template <class T> using mpq = priority_queue<T, vector<T>, greater<T>>;

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vl = vector<ll>;
using vi = vector<int>;

int main(int argc, char **argv)
{
    int n;
    string s1, s2;
    cin >> s1 >> s2;
    n = s1.size();
    // 00 0, 0X 1, X0 2, XX 3
    using a4i = array<int, 4>;
    vector<a4i> dp(n + 1);
    dp[0] = {0, 0, 0, 1};
    for (int i = 0; i < n; ++i) {
        int state = (s1[i] == 'X' ? 2 : 0) + (s2[i] == 'X' ? 1 : 0);
        dp[i + 1][state] = max({dp[i][0], dp[i][1], dp[i][2], dp[i][3]});
        switch (state) {
            case 0:
                dp[i + 1][1] = max(dp[i + 1][1], dp[i][0] + 1);
                dp[i + 1][2] = max(dp[i + 1][2], dp[i][0] + 1);
                dp[i + 1][3] = max(dp[i + 1][3], max(dp[i][1], dp[i][2]) + 1);
                break;
            case 1:
                dp[i + 1][0] = dp[i + 1][2] = 0;
                dp[i + 1][3] = max(dp[i + 1][3], dp[i][0] + 1);
                break;
            case 2:
                dp[i + 1][0] = dp[i + 1][1] = 0;
                dp[i + 1][3] = max(dp[i + 1][3], dp[i][0] + 1);
                break;
            case 3:
                dp[i + 1][0] = dp[i + 1][1] = dp[i + 1][2] = 0;
                break;
        }
    }
    for (auto x : dp)
        dbg(x);
    cout << max({dp[n][0], dp[n][1], dp[n][2], dp[n][3]}) - 1 << endl;
    return 0;
};