Submission #1306893

#	Time	Username	Problem	Language	Result	Execution time	Memory
1306893		Double_Slash	Lamps (JOI19_lamps)	C++20	10 / 100	700 ms	4200 KiB

lamp

#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));
}

• Subtask 1: 6 / 6
• Subtask 2: 0 / 41
• Subtask 3: 4 / 4
• Subtask 4: 0 / 49