Submission #104559

#TimeUsernameProblemLanguageResultExecution timeMemory
104559minhtung0404Lamps (JOI19_lamps)C++17
100 / 100
112 ms27932 KiB
#include<bits/stdc++.h>
const int N = 1e6 + 5;
const int inf = 1e9 + 7;
using namespace std;

string s, x;
int n, dp[N][3][2], ans = inf;

char cal(char c, int i, int j){
    if (i != 2) c = i + '0';
    if (j) c = '1' + '0' - c;
    return c;
}

void up(int&a, int b){
    if (a > b) a = b;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n >> s >> x; s = '.' + s; x = '.' + x;
    for (int i = 0; i < N; i++) for (int j = 0; j < 3; j++) for (int k = 0; k < 2; k++) dp[i][j][k] = inf;
    dp[0][2][0] = 0;
    for (int i = 1; i <= n; i++){
        for (int j = 0; j < 3; j++){
            for (int k = 0; k < 2; k++){
                if (cal(s[i], 0, k) == x[i]) up(dp[i][0][k], dp[i-1][j][k] + (j != 0));
                if (cal(s[i], 1, k) == x[i]) up(dp[i][1][k], dp[i-1][j][k] + (j != 1));
                if (cal(s[i], 2, k) == x[i]) up(dp[i][2][k], dp[i-1][j][k]);

                if (cal(s[i], 0, k ^ 1) == x[i]) up(dp[i][0][k ^ 1], dp[i-1][j][k] + (j != 0) + (k == 0));
                if (cal(s[i], 1, k ^ 1) == x[i]) up(dp[i][1][k ^ 1], dp[i-1][j][k] + (j != 1) + (k == 0));
                if (cal(s[i], 2, k ^ 1) == x[i]) up(dp[i][2][k ^ 1], dp[i-1][j][k] + (k == 0));
            }
        }
    }
    for (int i = 0; i < 3; i++) for (int j = 0; j < 2; j++) up(ans, dp[n][i][j]);
    cout << ans;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...