Submission #104559

#	Time	Username	Problem	Language	Result	Execution time	Memory
104559		minhtung0404	Lamps (JOI19_lamps)	C++17	100 / 100	112 ms	27932 KiB

lamp

#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;
}

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