Submission #1206485

#	Time	Username	Problem	Language	Result	Execution time	Memory
1206485		Hamed_Ghaffari	Lamps (JOI19_lamps)	C++20	100 / 100	47 ms	21876 KiB

lamp

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

#define mins(a, b) (a = min(a, b));

const int MXN = 1e6+5;

int n, dp[MXN][5];
bool A[MXN], B[MXN];

int32_t main() {
    cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
    cin >> n;
    for(int i=0; i<n; i++) {
        char c;
        cin >> c;
        A[i] = c=='1';
    }
    for(int i=0; i<n; i++) {
        char c;
        cin >> c;
        B[i] = c=='1';
    }
    dp[0][0] = A[0]^B[0];
    dp[0][1] = 1 + (1^B[0]);
    dp[0][2] = 1 + (0^B[0]);
    dp[0][3] = 2 + (1^B[0]);
    dp[0][4] = 2 + (0^B[0]);
    auto cost = [&](int i, bool x, bool y) -> bool {
        return B[i]==x && B[i+1]!=y;
    };
    for(int i=1; i<n; i++) {
        dp[i][0] = min({
            dp[i-1][0] + cost(i-1, A[i-1], A[i]),
            dp[i-1][1] + cost(i-1, 1, A[i]),
            dp[i-1][2] + cost(i-1, 0, A[i]),
            dp[i-1][3] + cost(i-1, 1, A[i]),
            dp[i-1][4] + cost(i-1, 0, A[i])
        });
        
        dp[i][1] = min({
            dp[i-1][0] + 1 + cost(i-1, A[i-1], 1),
            dp[i-1][1] + cost(i-1, 1, 1),
            dp[i-1][2] + 1 + cost(i-1, 0, 1),
            dp[i-1][3] + cost(i-1, 1, 1),
            dp[i-1][4] + cost(i-1, 0, 1)
        });

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

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

        dp[i][4] = min({
            dp[i-1][0] + 2 + cost(i-1, A[i-1], 0),
            dp[i-1][1] + 1 + cost(i-1, 1, 0),
            dp[i-1][2] + 1 + cost(i-1, 0, 0),
            dp[i-1][3] + 1 + cost(i-1, 1, 0),
            dp[i-1][4] + cost(i-1, 0, 0)
        });
    }
    cout << *min_element(dp[n-1], dp[n-1]+5) << '\n';
    return 0;
}

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