Submission #941448

#	Time	Username	Problem	Language	Result	Execution time	Memory
941448		juliany2	Lamps (JOI19_lamps)	C++17	100 / 100	39 ms	4768 KiB

lamp

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(x) (x).begin(), (x).end()

void ckmin(int &x, int y) {
    x = min(x, y);
}

int main() {
    cin.tie(0)->sync_with_stdio(false);

    int n;
    string a, b;
    cin >> n >> a >> b;

    vector<vector<int>> dp(2, vector<int> (3, 1e9));
    dp[0][0] = 0;

    for (int i = 0; i < n; i++) {
        for (int x : {0, 1})
            for (int y : {0, 1, 2})
                ckmin(dp[x][0], dp[x][y]);

        for (int y : {0, 1, 2})
            ckmin(dp[0][y], dp[1][y]);

        for (int x : {0, 1})
            for (int y : {1, 2})
                ckmin(dp[x][y], dp[x][0] + 1);

        for (int y : {0, 1, 2})
            ckmin(dp[1][y], dp[0][y] + 1);

        for (int x : {0, 1}) {
            for (int y : {0, 1, 2}) {
                char have = (y == 0 ? a[i] : (y - 1 + '0'));
                if ((have == b[i]) == x)
                    dp[x][y] = 1e9;
            }
        }
    }

    int ans = 1e9;
    for (int x : {0, 1})
        for (int y : {0, 1, 2})
            ans = min(ans, dp[x][y]);

    cout << ans << '\n';

    return 0;
}

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