Submission #428841

#	Time	Username	Problem	Language	Result	Execution time	Memory
428841		tengiz05	Lamps (JOI19_lamps)	C++17	100 / 100	149 ms	35604 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];
                    for (int A0 = 0; A0 < 2; A0++) {
                        for (int A1 = 0; A1 < 2; A1++) {
                            for (int XR = 0; XR < 2; XR++) {
                                int cost = dp[i - 1][A0][A1][XR];
                                if (a0 > A0) cost++;
                                if (a1 > A1) cost++;
                                if (xr > XR) cost++;
                                ret = std::min(ret, cost);
                            }
                        }
                    }
                }
    }
    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: 6 / 6
• Subtask 2: 41 / 41
• Subtask 3: 4 / 4
• Subtask 4: 49 / 49