Submission #1308449

#	Time	Username	Problem	Language	Result	Execution time	Memory
1308449		purplelemon	Lamps (JOI19_lamps)	C++20	100 / 100	58 ms	95464 KiB

lamp

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define eq(x) (A[i]==B[i]?x:1e18)
#define dif(x) (A[i]!=B[i]?x:1e18)
#define OP(i,j,k,x) dp[i][j][k] = min(dp[i][j][k],x);

const int N = 1e6 + 10;
int n;
int A[N], B[N], dp[N][5][2];


void solve() {
    cin >> n;
    string str;
    cin >> str;
    for (int i = 1;i <= n;i++) {
        A[i] = str[i-1]-'0';
    }
    cin >> str;
    for (int j = 1;j <= n;j++) {
        B[j] = str[j-1]-'0';
    }
    memset(dp,63,sizeof(dp));
    dp[1][0][0] = (A[1]!=B[1]);
    if (A[1] != B[1]) {
        dp[1][1][0] = 0;
        dp[1][1][1] = 0;
    }
    dp[1][2][0] = 0;
    dp[1][2][1] = 0;
    if (A[1] == B[1]) {
        dp[1][3][0] = 0;
        dp[1][3][1] = 0;
    } else {
        dp[1][3][B[1]] = 0;
        dp[1][3][1-B[1]] = 1;
    }
    dp[1][4][0] = 0;


    for (int i = 2;i <= n;i++) {
        if (A[i] == B[i]) dp[i][0][0] = min(dp[i][0][0],dp[i-1][0][0]);
        dp[i][0][0] = min(dp[i][0][0], 1 + dp[i-1][3][B[i]]);
        if (A[i] != B[i]) dp[i][0][0] = min(dp[i][0][0],1+dp[i-1][4][0]);

        if (B[i] == B[i+1]) {
            dp[i][1][1-B[i]] = dp[i-1][1][1-B[i]];
        }
        if (A[i] != B[i]) {
            dp[i][1][0] = min(dp[i][1][0],dp[i-1][4][0]);
            dp[i][1][1] = min(dp[i][1][1],dp[i-1][4][0]);
        }

        if (B[i] == B[i+1]) dp[i][2][1-B[i]] = dp[i-1][2][1-B[i]];
        dp[i][2][B[i]] = min(dp[i][2][B[i]],dp[i-1][3][B[i]]);
        if (A[i] != B[i]) {
            dp[i][2][0] = min(dp[i][2][0],dp[i-1][4][0]);
            dp[i][2][1] = min(dp[i][2][1],dp[i-1][4][0]);
        }

        dp[i][3][0] = dp[i-1][3][0];
        dp[i][3][1] = dp[i-1][3][1];
        if (B[i] != B[i+1]) {
            dp[i][3][1-B[i]]++;
        }
        if (A[i] != B[i]) {
            dp[i][3][0] = min(dp[i][3][0],1+dp[i-1][4][0]);
            dp[i][3][1] = min(dp[i][3][1],1+dp[i-1][4][0]);
        }
        if (A[i] == B[i]) {
            dp[i][3][0] = min(dp[i][3][0],dp[i-1][0][0]);
            dp[i][3][1] = min(dp[i][3][1],dp[i-1][0][0]);
        }
        dp[i][3][1-B[i]] = min(dp[i][3][1-B[i]],1+dp[i-1][2][1-B[i]]);

        if (A[i] != B[i]) {
            dp[i][4][0] = dp[i-1][4][0];
        }
        if (A[i] == B[i]) {
            dp[i][4][0] = min(dp[i][4][0],dp[i-1][0][0]);
        }
        dp[i][4][0] = min(dp[i][4][0],1+dp[i-1][2][1-B[i]]);
        dp[i][4][0] = min(dp[i][4][0],1+dp[i-1][3][B[i]]); 
    }
    cout << dp[n][0][0];
}

int32_t main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    solve();
}

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