Submission #1151181

#	Time	Username	Problem	Language	Result	Execution time	Memory
1151181		weakweakweak	Lamps (JOI19_lamps)	C++20	100 / 100	71 ms	59136 KiB

lamp

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

int n;
string a, b;
int dp[1210000][2][3][2] = {0};

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);
    cin >> n >> a >> b;
    for (char &c : a) c -= '0';
    for (char &c : b) c -= '0';
    a = "$"+a, b = "$"+b;
    memset(dp, 63, sizeof(dp));
    dp[0][0][2][0] = 0;

    for (int i = 1; i <= n; i++) {
        for (int lst = 0; lst <= 2; lst++) {
            if (a[i] == b[i]) {
                int z = min(min(dp[i-1][1][lst][0], dp[i-1][0][lst][0]), min(dp[i-1][1][lst][1], dp[i-1][0][lst][1]));
                dp[i][0][2][0] = min(dp[i][0][2][0], z);
            }
            if (b[i] == 0) {
                for (int f = 0; f < 1; f++) {
                    dp[i][0][0][f] = min(dp[i][0][0][f], dp[i-1][0][lst][f] + !(lst==0));
                    dp[i][1][0][f] = min(dp[i][1][0][f], dp[i-1][1][lst][f] + !(lst==0));
                    dp[i][1][0][f] = min(dp[i][1][0][f], dp[i-1][0][1][f]+1 );
                }
                dp[i][1][1][1] = min(dp[i][1][1][1], dp[i-1][1][1][1]);
                dp[i][1][1][1] = min(dp[i][1][1][1], dp[i-1][1][lst][0]+1);
                dp[i][1][1][1] = min(dp[i][1][1][1], dp[i-1][0][0][0]+1);
                dp[i][0][0][0] = min(dp[i][0][0][0], dp[i-1][1][0][1]);
                dp[i][0][0][0] = min(dp[i][0][0][0], dp[i-1][1][1][0]);

                
                dp[i][1][0][0] = min(dp[i][1][0][0], dp[i-1][1][0][0]);
                dp[i][1][0][0] = min(dp[i][1][0][0], dp[i-1][0][0][0] + 1);
            }
            if (b[i] == 1) {
                for (int f = 0; f < 1; f++) {
                    dp[i][0][1][f] = min(dp[i][0][1][f], dp[i-1][0][lst][f] + !(lst==1));
                    dp[i][1][1][f] = min(dp[i][1][1][f], dp[i-1][1][lst][f] + !(lst==1));
                    dp[i][1][1][f] = min(dp[i][1][1][f], dp[i-1][0][0][f]+1 );
                }
                dp[i][1][0][1] = min(dp[i][1][0][1], dp[i-1][1][0][1]);
                dp[i][1][0][1] = min(dp[i][1][0][1], dp[i-1][1][lst][0]+1);
                dp[i][1][0][1] = min(dp[i][1][0][1], dp[i-1][0][1][0]+1);
                dp[i][0][1][0] = min(dp[i][0][1][0], dp[i-1][1][1][1]);
                dp[i][0][1][0] = min(dp[i][0][1][0], dp[i-1][1][0][0]);

                dp[i][1][1][0] = min(dp[i][1][1][0], dp[i-1][1][1][0]);
                dp[i][1][1][0] = min(dp[i][1][1][0], dp[i-1][0][1][0] + 1);
            }
            if (a[i] != b[i]) {
                dp[i][1][2][0] = min(dp[i][1][2][0], min(dp[i-1][1][lst][0], dp[i-1][0][lst][0]+1));
            }
        } 
    }

    int ans = INT_MAX;
    for (int j = 0; j < 3; j++) {
        // cout << dp[n-4][0][j][0] << ' ' << dp[n-4][1][j][0] << ' ' << dp[n-4][0][j][1] << ' ' << dp[n-4][1][j][1] << '\n';
        ans = min(ans, min(dp[n][0][j][0], dp[n][1][j][0]));
        ans = min(ans, min(dp[n][0][j][1], dp[n][1][j][1]));
    }
    // cout << dp[4][1][0][0] << '\n';
    cout << ans << '\n';
}
/*
10111110

5
00110
01111
10011

5
00110
10011

15
10 1 1 1 10
10 0 1 0 10

6
100101
001000
*/

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