Submission #1276754

#	Time	Username	Problem	Language	Result	Execution time	Memory
1276754		duckindog	Lamps (JOI19_lamps)	C++20	100 / 100	46 ms	20004 KiB

lamp

#include <bits/stdc++.h>

using namespace std;

const int N = 1'000'000 + 10;
int n;
int a[N], b[N];

const int MAX = 1'000'000'000;
int f[N][3];

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

    cin >> n;
    for (int i = 1; i <= n; ++i) { 
        char ch; cin >> ch;
        a[i] = (ch == '1');
    }
    for (int i = 1; i <= n; ++i) { 
        char ch; cin >> ch;
        b[i] = (ch == '1');
    }

    auto useXor = [&](int i, int j) { 
        return !j ? a[i] != b[i] : (j - 1 != b[i]);
    };

    memset(f, 63, sizeof f);

    f[1][0] = useXor(1, 0);
    f[1][1] = 1 + useXor(1, 1);
    f[1][2] = 1 + useXor(1, 2);
    for (int i = 2; i <= n; ++i) { 
        { // f[i][0] no assign line
            auto& ret = f[i][0];
            for (int j = 0; j <= 2; ++j) { 
                ret = min(ret, f[i - 1][j] + (useXor(i, 0) && !useXor(i - 1, j)));
            }
        }

        { // f[i][1] assign line is 0
            auto& ret = f[i][1];
            for (int j = 0; j <= 2; ++j) { 
                ret = min(ret, f[i - 1][j] + (j != 1) + (useXor(i, 1) && !useXor(i - 1, j)));
            }
        }

        { // f[i][1] assign line is 1
            auto& ret = f[i][2];
            for (int j = 0; j <= 2; ++j) { 
                ret = min(ret, f[i - 1][j] + (j != 2) + (useXor(i, 2) && !useXor(i - 1, j)));
            }
        }
    }
    
    cout << min({f[n][0], f[n][1], f[n][2]}) << "\n";
}

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