Submission #384794

#TimeUsernameProblemLanguageResultExecution timeMemory
384794kostia244Lamps (JOI19_lamps)C++17
4 / 100
60 ms26044 KiB
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 12;
int dp[maxn][3][2];
void minq(int &a, int b) {
    a = min(a, b);
}
int main() {
    cin.tie(0)->sync_with_stdio(0);
    int n;
    string a, b;
    cin >> n >> a >> b;
    memset(dp, 0x3f, sizeof dp);
    dp[0][0][0] = 0;
    for(int i = 0; i < n; i++) {
        for(int lst = 0; lst < 3; lst++) {
            dp[i][lst][0] = min(dp[i][lst][0], dp[i][lst][1]);
            dp[i][lst][1] = min(dp[i][lst][1], dp[i][lst][0]+1);
            for(int rev = 0; rev < 2; rev++) {
                int cur = (a[i]-'0')^rev;
                int targ = b[i]-'0';
                if((cur == targ && !lst) || lst-1 == targ)
                    minq(dp[i+1][lst][rev], dp[i][lst][rev]);
                if(cur == targ)
                    minq(dp[i+1][0][rev], dp[i][lst][rev]);
                minq(dp[i+1][1+targ][rev], dp[i][lst][rev]+1);
            }
        }
    }
    int ans = 69<<20;
    for(int i = 0; i < 3; i++)
        for(int j = 0; j < 2; j++)
            ans = min(dp[n][i][j], ans);
    cout << ans << '\n';
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...