Submission #422504

#	Time	Username	Problem	Language	Result	Execution time	Memory
422504		qwerasdfzxcl	Lamps (JOI19_lamps)	C++14	100 / 100	136 ms	71036 KiB

lamp

#include <bits/stdc++.h>

typedef long long ll;
using namespace std;
string x, y;
int dp0[1001000], dp1[1001000][3], dp2[1001000][3][3], ans[1001000], dp2mn[1001000][3];

void getmn(int x){
    for (int i=0;i<3;i++){
        ans[x] = min(ans[x], dp1[x][i]);
        for (int j=0;j<3;j++){
            dp2mn[x][i] = min(dp2mn[x][i], dp2[x][i][j]);
            dp2mn[x][j] = min(dp2mn[x][j], dp2[x][i][j]);
            ans[x] = min(ans[x], dp2[x][i][j]);
        }
    }
    ans[x] = min(ans[x], dp0[x]);
}

int main(){
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    int n;
    cin >> n >> x >> y;
    for (int i=0;i<n;i++){
        dp0[i] = 1e9;
        ans[i] = 1e9;
        fill(dp1[i], dp1[i]+3, 1e9);
        fill(dp2mn[i], dp2mn[i]+3, 1e9);
        for (int j=0;j<3;j++) fill(dp2[i][j], dp2[i][j]+3, 1e9);
    }
    if (x[0]==y[0]) dp0[0] = 0, dp2[0][2][2] = 2;
    else dp1[0][2] = 1, dp2[0][0][2] = 2, dp2[0][1][2] = 2;
    dp1[0][y[0]-'0'] = 1;
    for (int j=0;j<3;j++) dp2[0][j][y[0]-'0'] = 2;
    dp2[0][(y[0]-'0')^1][2] = 2;
    getmn(0);

    for (int i=1;i<n;i++){
        if (x[i]==y[i]) dp0[i] = ans[i-1];
        else dp1[i][2] = min(ans[i-1]+1, min(dp1[i-1][2], dp2mn[i-1][2]));
        dp1[i][y[i]-'0'] = min(ans[i-1]+1, min(dp1[i-1][y[i]-'0'], dp2mn[i-1][y[i]-'0']));

        for (int j=0;j<3;j++){
            int val1 = min(min(dp1[i-1][j], dp1[i-1][y[i]-'0']), min(dp2mn[i-1][j], dp2mn[i-1][y[i]-'0']));
            dp2[i][j][y[i]-'0'] = min(ans[i-1]+2, min(val1+1, dp2[i-1][j][y[i]-'0']));
        }
        int val = min(min(dp1[i-1][2], dp1[i-1][(y[i]-'0')^1]), min(dp2mn[i-1][2], dp2mn[i-1][(y[i]-'0')^1]));
        dp2[i][(y[i]-'0')^1][2] = min(ans[i-1]+2, min(val+1, dp2[i-1][(y[i]-'0')^1][2]));

        if (x[i]==y[i]){
            int val2 = min(dp1[i-1][2], dp2mn[i-1][2]);
            dp2[i][2][2] = min(ans[i-1]+2, min(val2+1, dp2[i-1][2][2]));
        }

        getmn(i);
    }
/*
    for (int i=0;i<n;i++) printf("%d ", dp0[i]);
    printf("\n\n");
    for (int j=0;j<3;j++){
        for (int i=0;i<n;i++) printf("%d ", dp1[i][j]);
        printf("\n");
    }
    printf("\n");
    for (int j=0;j<3;j++){
        for (int k=0;k<3;k++){
            for (int i=0;i<n;i++) printf("%d ", dp2[i][j][k]);
            printf("\n");
        }
    }
    printf("\n");
    for (int i=0;i<n;i++) printf("%d ", ans[i]);
    printf("\n\n");
*/
    cout << ans[n-1];
    return 0;
}

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