제출 #1332306

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1332306		MisterReaper	Lamps (JOI19_lamps)	C++20	100 / 100	224 ms	151132 KiB

lamp

#include <bits/stdc++.h>

using i64 = long long;

#ifdef DEBUG
    #include "debug.h"
#else
    #define debug(...) void(23)
#endif

template<typename T>
bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int N;
    std::cin >> N;

    std::string S, T;
    std::cin >> S >> T;

    std::vector f(N + 1, std::vector(2, std::vector(3, N)));
    f[0][0][0] = 0;
    for (int i = 0; i < N; ++i) {
        for (int x = 0; x < 2; ++x) {
            for (int y = 0; y < 3; ++y) {
                for (int a = 0; a < 2; ++a) {
                    for (int b = 0; b < 3; ++b) {
                        if (a == 0) {
                            if (b == 0) {
                                if (S[i] != T[i]) {
                                    continue;
                                }
                            } else if (b == 1) {
                                if (T[i] != '0') {
                                    continue;
                                }
                            } else {
                                if (T[i] != '1') {
                                    continue;
                                }
                            }
                        } else {
                            if (b == 0) {
                                if (S[i] == T[i]) {
                                    continue;
                                }
                            } else if (b == 1) {
                                if (T[i] == '0') {
                                    continue;
                                }
                            } else {
                                if (T[i] == '1') {
                                    continue;
                                }
                            }
                        }
                        int cost = (x == 0 && a == 1) + (y != b && b != 0);
                        chmin(f[i + 1][a][b], f[i][x][y] + cost);
                    }
                }
            }
        }
    }

    int ans = N;
    for (int i = 0; i < 2; ++i) {
        for (int j = 0; j < 3; ++j) {
            chmin(ans, f[N][i][j]);
        }
    }

    std::cout << ans << '\n';

    return 0;
}

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