제출 #1127252

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1127252		OI_Account	Lamps (JOI19_lamps)	C++20	100 / 100	73 ms	47308 KiB

lamp

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

typedef long long ll;

const int N = 1'000'000;
const int INF = 1'000'000'000;

int n, a[N + 10], b[N + 10];
int dp[N + 10], x[N + 10];
int c[N + 10][4][2];

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

int check(int i, int t, int j, int add = 0) {
    if (add + j == 2)
        return c[i][t][j] - 1;
    return c[i][t][j] - (add + j == 1 && t == 2);
}

void calcDP(int i) {
    if (a[i] != b[i]) {
        dp[i] = INF;
        return;
    }
    if (i == 1) {
        dp[i] = 0;
        return;
    }
    dp[i] = min(dp[i - 1], x[i - 1]);
    for (int t = 1; t <= 3; t++)
        for (int j = 0; j <= 1; j++)
            dp[i] = min(dp[i], check(i - 1, t, j));
}

void calcX(int i) {
    if (a[i] == b[i]) {
        x[i] = INF;
        return;
    }
    if (i == 1) {
        x[i] = 1;
        return;
    }
    x[i] = min(x[i - 1], dp[i - 1] + 1);
    for (int t = 1; t <= 3; t++)
        for (int j = 0; j <= 1; j++)
            x[i] = min(x[i], check(i - 1, t, j, 1) + 1);
}

void calcC1(int i) {
    if (i == 1) {
        c[i][1][0] = 1;
        c[i][1][1] = INF;
        return;
    }
    c[i][1][0] = dp[i - 1] + 1;
    c[i][1][1] = x[i - 1] + 1;
    if (b[i] == b[i - 1]) {
        c[i][1][0] = min(c[i][1][0], c[i - 1][1][0]);
        c[i][1][1] = min(c[i][1][1], c[i - 1][1][1]);
    }
}

void calcC23(int i) {
    if (i == 1) {
        for (int t = 2; t <= 3; t++)
            c[i][t][0] = c[i][t][1] = INF;
        return;
    }
    if (b[i] == b[i - 1]) {
        for (int t = 2; t <= 3; t++) {
            c[i][t][0] = c[i - 1][t][0];
            c[i][t][1] = c[i - 1][t][1];
        }
    }
    else {
        for (int j = 0; j <= 1; j++) {
            c[i][2][j] = min(c[i - 1][1][j], c[i - 1][3][j]) + 1;
            c[i][3][j] = c[i - 1][2][j];
        }
    }
}

void calcAns() {
    for (int i = 1; i <= n; i++) {
        calcDP(i);
        calcX(i);
        calcC1(i);
        calcC23(i);
    }
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    readInput();
    calcAns();
    cout << dp[n] << flush;
    return 0;
}

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