Submission #1207133

#	Time	Username	Problem	Language	Result	Execution time	Memory
1207133		VMaksimoski008	Lamps (JOI19_lamps)	C++20	100 / 100	55 ms	4156 KiB

lamp

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

int main() {
    int n, ans=1e9; cin >> n;
    string a, b; cin >> a >> b;
    a = "." + a;
    b = "." + b;

    int dp[3][2], ndp[3][2];
    for(int i=0; i<3; i++)
        for(int j=0; j<2; j++) dp[i][j] = 1e9;
    dp[0][0] = 0;

    for(int i=1; i<=n; i++) {
        for(int j=0; j<3; j++) {
            for(int k=0; k<2; k++) {
                ndp[j][k] = 1e9;

                int v = a[i] - '0';
                if(j) v = j - 1;
                if(k) v ^= 1;
                
                if(v != b[i] - '0') continue;

                for(int pj=0; pj<3; pj++)
                    for(int pk=0; pk<2; pk++)
                        ndp[j][k] = min(ndp[j][k], dp[pj][pk] + (j && pj != j) + (k && !pk));
            }
        }
        swap(dp, ndp);
    }

    for(int i=0; i<3; i++)
        for(int j=0; j<2; j++) ans = min(ans, dp[i][j]);
    cout << ans << '\n';
}

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