Submission #659924

#TimeUsernameProblemLanguageResultExecution timeMemory
659924cristi_aLamps (JOI19_lamps)C++17
4 / 100
23 ms19904 KiB
#include <bits/stdc++.h>
using namespace std;
const int nmax = 1e6;
const int inf = 1e9;

int dp[nmax+5][4];
// 0 nimic
// 1 off
// 2 on
// 3 toggle

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n; string a, b; cin >> n >> a >> b;
    a = " " + a; b = " " + b;
    for(int i=0; i<=n; i++)
        for(int j=0; j<=3; j++)
            dp[i][j] = inf;
    dp[0][0] = 0;
    for(int i=1; i<=n; i++) {
        if(a[i] == '0' and b[i] == '0') {
            dp[i][0] = min({dp[i-1][0], dp[i-1][1], dp[i-1][2], dp[i-1][3]});
            dp[i][1] = min({dp[i-1][0] + 1, dp[i-1][1], dp[i-1][2] + 1, dp[i-1][3] + 1});
        }
        else if(a[i] == '0' and b[i] == '1') {
            dp[i][2] = min({dp[i-1][0] + 1, dp[i-1][1] + 1, dp[i-1][2], dp[i-1][3] + 1});
            dp[i][3] = min({dp[i-1][0] + 1, dp[i-1][1] + 1, dp[i-1][2] + 1, dp[i-1][3]});
        }
        else if(a[i] == '1' and b[i] == '0') {
            dp[i][1] = min({dp[i-1][0] + 1, dp[i-1][1], dp[i-1][2] + 1, dp[i-1][3] + 1});
            dp[i][3] = min({dp[i-1][0] + 1, dp[i-1][1] + 1, dp[i-1][2] + 1, dp[i-1][3]});
        }
        else if(a[i] == '1' and b[i] == '1') {
            dp[i][0] = min({dp[i-1][0], dp[i-1][1], dp[i-1][2], dp[i-1][3]});
            dp[i][2] = min({dp[i-1][0] + 1, dp[i-1][1] + 1, dp[i-1][2], dp[i-1][3] + 1});
        }
    }
    cout << min({dp[n][0], dp[n][1], dp[n][2], dp[n][3]});
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...