Submission #428757

#	Time	Username	Problem	Language	Result	Execution time	Memory
428757		tengiz05	Lamps (JOI19_lamps)	C++17	4 / 100	102 ms	35576 KiB

lamp

#include <bits/stdc++.h>
constexpr int N = 1000000;
int dp[N + 1][2][2][2];
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int n;
    std::cin >> n;
    std::string a, b;
    std::cin >> a >> b;
    a = "#" + a;
    b = "#" + b;
    // [pos][0][1][xor]
    memset(dp, 0x3f, sizeof dp);
    dp[0][0][0][0] = 0;
    for (int i = 1; i <= n; i++) {
        for (int a0 = 0; a0 < 2; a0++)
            for (int a1 = 0; a1 < 2; a1++)
                for (int xr = 0; xr < 2; xr++) {
                    char t = a[i];
                    if (a0) t = '0';
                    if (a1) t = '1';
                    if (xr) t ^= 1;
                    if (t != b[i]) {
                        continue;
                    }
                    int &ret = dp[i][a0][a1][xr];
                    ret = dp[i - 1][a0][a1][xr] - a0 - a1 - xr;
                    ret = std::min(ret, dp[i - 1][0][a1][xr] - a1 - xr);
                    ret = std::min(ret, dp[i - 1][a0][0][xr] - a0 - xr);
                    ret = std::min(ret, dp[i - 1][0][0][xr] - xr);
                    ret = std::min(ret, dp[i - 1][0][a1][0] - a1);
                    ret = std::min(ret, dp[i - 1][a0][0][0] - a0);
                    ret = std::min(ret, dp[i - 1][0][0][0]);
                    ret = std::min(ret, dp[i - 1][1][a1][xr] - a1 - xr);
                    ret = std::min(ret, dp[i - 1][a0][1][xr] - a0 - xr);
                    ret = std::min(ret, dp[i - 1][1][1][xr] - xr);
                    ret = std::min(ret, dp[i - 1][1][a1][1] - a1);
                    ret = std::min(ret, dp[i - 1][a0][1][1] - a0);
                    ret = std::min(ret, dp[i - 1][1][1][1]);
                    ret += a0 + a1 + xr;
                }
    }
    int ans = n;
    for (int a0 = 0; a0 < 2; a0++)
        for (int a1 = 0; a1 < 2; a1++)
            for (int xr = 0; xr < 2; xr++)
                ans = std::min(ans, dp[n][a0][a1][xr]);
    std::cout << ans << "\n";
    return 0;
}

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