Submission #874040

#	Time	Username	Problem	Language	Result	Execution time	Memory
874040		vjudge1	Lamps (JOI19_lamps)	C++17	100 / 100	54 ms	27908 KiB

lamp

#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 10;
const int INF = 1e9;

string s1, s2;
int n, dp[N][3][2], ans = INF;

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

int main() {
    ios:: sync_with_stdio(0), cin.tie(0);
    cin >> n >> s1 >> s2;
	s1 = 'D' + s1; s2 = 'D' + s2;
    memset(dp, 63, sizeof dp);
    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 (f(s1[i], 0, k) == s2[i]) dp[i][0][k] = min(dp[i][0][k], dp[i-1][j][k] + (j != 0));
                if (f(s1[i], 1, k) == s2[i]) dp[i][1][k] = min(dp[i][1][k], dp[i-1][j][k] + (j != 1));
                if (f(s1[i], 2, k) == s2[i]) dp[i][2][k] = min(dp[i][2][k], dp[i-1][j][k]);
                if (f(s1[i], 0, k ^ 1) == s2[i]) dp[i][0][k ^ 1] = min(dp[i][0][k ^ 1], dp[i - 1][j][k] + (j ^ 0) + !(k ^ 0));
                if (f(s1[i], 1, k ^ 1) == s2[i]) dp[i][1][k ^ 1] = min(dp[i][1][k ^ 1], dp[i - 1][j][k] + (j ^ 1) + !(k ^ 0));
                if (f(s1[i], 2, k ^ 1) == s2[i]) dp[i][2][k ^ 1] = min(dp[i][2][k ^ 1], dp[i - 1][j][k] + !(k ^ 0));
				if (i == n) ans = min(ans, dp[i][j][k]);
            }
    cout << ans << '\n';
}

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