Submission #1306893

#TimeUsernameProblemLanguageResultExecution timeMemory
1306893Double_SlashLamps (JOI19_lamps)C++20
10 / 100
700 ms4200 KiB
#include <bits/stdc++.h>

using namespace std;
#define all(x) x.begin(), x.end()

int main() {
    vector<basic_string<int>> cc{{}};
    basic_string<int> v;
    for (int a = 0; a <= 2; ++a) {
        cc.emplace_back(v += a);
        for (int b = 0; b <= 2; ++b) {
            if (b == a) continue;
            cc.emplace_back(v += b);
            for (int c = 1; c <= 2; ++c) {
                if (c != b and not min({a, b, c})) cc.emplace_back(v + c);
            }
            v.pop_back();
        }
        v.pop_back();
    }
    int adj[cc.size()][cc.size()];
    for (int i = cc.size(); i--;) {
        for (int j = cc.size(); j--;) {
            adj[i][j] = cc[j].size();
            for (int x = 0, y = 0; y < cc[j].size(); ++y) {
                while (x < cc[i].size() and cc[i][x] != cc[j][y]) ++x;
                x++ < cc[i].size() and --adj[i][j];
            }
        }
    }
    int n;
    string a, b;
    cin >> n;
    cin >> a >> b;
    vector dp(cc.size(), n);
    for (int i = dp[0] = 0; i < n; ++i) {
        vector dp2(cc.size(), n);
        for (int j = cc.size(); j--;) {
            for (int k = cc.size(); k--;) {
                bool c = a[i] - '0';
                for (int x: cc[k]) c = x ? x - 1 : c ^ 1;
                c == b[i] - '0' and (dp2[k] = min(dp2[k], dp[j] + adj[j][k]));
            }
        }
        dp = move(dp2);
    }
    cout << *min_element(all(dp));
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...