Submission #1296301

#TimeUsernameProblemLanguageResultExecution timeMemory
1296301takoshanavaLamps (JOI19_lamps)C++20
0 / 100
30 ms6452 KiB
#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define fs first
#define sc second
using namespace std;

const int N = 1e5 + 5;
int dp[N][5];
vector<int> vec{0, 1, 2};

signed main() {
    int n;
    string a, b;
    cin >> n >> a >> b;

    for(int i = 0; i < N; i++){
        for(int j = 0; j < 5; j++) dp[i][j] = N;
    }

    dp[0][2] = 0;

    for(int i = 1; i <= n; i++){
        for(auto k:vec){
            char p = k + '0';
            if (i > 1 and k == 2) p = a[i - 2];

            for(auto v:vec){
                int cnt = dp[i - 1][k];
                if(k != v and v != 2) cnt++;
                char c = v + '0';
                if(v == 2) c = a[i - 1];
                if(c != b[i - 1] and (i == 1 or p == b[i - 2])) cnt++;
                dp[i][k] = min(dp[i][k], cnt);
            }
        }
    }
    int ans = N;
    for(int i = 0; i < 3; i++) ans = min(ans, dp[n][i]);
    cout << ans << endl;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...