Submission #1306896

#	Time	Username	Problem	Language	Result	Execution time	Memory
1306896		Double_Slash	Lamps (JOI19_lamps)	C++20	100 / 100	219 ms	4272 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--;) {
            int dp[cc[i].size() + 1][cc[j].size() + 1]{};
            for (int x = 0; x < cc[i].size(); ++x) {
                for (int y = 0; y < cc[j].size(); ++y) dp[x + 1][y + 1] = cc[i][x] == cc[j][y] ? dp[x][y] + 1 : max(dp[x][y + 1], dp[x + 1][y]);
            }
            adj[i][j] = cc[j].size() - dp[cc[i].size()][cc[j].size()];
        }
    }
    int n;
    string a, b;
    cin >> n >> a >> b;
    vector dp(cc.size(), n);
    for (int i = dp[0] = 0; i < n; ++i) {
        vector dp2(cc.size(), n);
        for (int k = cc.size(); k--;) {
            bool c = a[i] - '0';
            for (int x: cc[k]) c = x ? x - 1 : c ^ 1;
            if (c != b[i] - '0') continue;
            for (int j = cc.size(); j--;) dp2[k] = min(dp2[k], dp[j] + adj[j][k]);
        }
        dp = move(dp2);
    }
    cout << *min_element(all(dp));
}

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