Submission #823474

#TimeUsernameProblemLanguageResultExecution timeMemory
823474LucaIlieLamps (JOI19_lamps)C++17
100 / 100
75 ms33744 KiB
#include <bits/stdc++.h>

using namespace std;

const int ON0 = 1;
const int ON1 = 0;
const int OFF = 2;
const int MAX_N = 1e6;
int initial[MAX_N + 1], corect[MAX_N + 1];
int dp[MAX_N + 1][3][2];

int main() {
    int n;
    string a, b;

    cin >> n >> a >> b;
    initial[0] = corect[0] = 0;
    for ( int i = 0; i < n; i++ ) {
        initial[i + 1] = a[i] - '0';
        corect[i + 1] = b[i] - '0';
    }

    for ( int i = 0; i <= n; i++ ) {
        for ( int s = 0; s < 3; s++ ) {
            for ( int b = 0; b < 2; b++ )
                dp[i][s][b] = n;
        }
    }
    dp[0][OFF][0] = 0;
    for ( int i = 1; i <= n; i++ ) {
        //OFF
        for ( int s = 0; s < 3; s++ ) {
            dp[i][OFF][initial[i]] = min( dp[i][OFF][initial[i]], dp[i - 1][s][corect[i - 1]] + (initial[i] != corect[i]) ); //era corect
            dp[i][OFF][initial[i]] = min( dp[i][OFF][initial[i]], dp[i - 1][s][corect[i - 1] ^ 1] ); //era gresit
        }

        //ON0
        for ( int s = 0; s < 3; s++ ) {
            dp[i][ON0][0] = min( dp[i][ON0][0], dp[i - 1][s][corect[i - 1]] + (s != ON0) + (corect[i] != 0) ); //era corect
            dp[i][ON0][0] = min( dp[i][ON0][0], dp[i - 1][s][corect[i - 1] ^ 1] + (s != ON0) ); //era gresit
        }

        //ON1
        for ( int s = 0; s < 3; s++ ) {
            dp[i][ON1][1] = min( dp[i][ON1][1], dp[i - 1][s][corect[i - 1]] + (s != ON1) + (corect[i] != 1) ); //era corect
            dp[i][ON1][1] = min( dp[i][ON1][1], dp[i - 1][s][corect[i - 1] ^ 1] + (s != ON1) ); //era gresit
        }
    }

    int minn = MAX_N;
    for ( int s = 0; s < 3; s++ ) {
        for ( int b = 0; b < 2; b++ )
            minn = min( minn, dp[n][s][b] );
    }

    cout << minn;

    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...