Submission #1211609

#TimeUsernameProblemLanguageResultExecution timeMemory
1211609JooDdaeLamps (JOI19_lamps)C++20
4 / 100
18 ms26008 KiB
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int n, dp[1001001][2][3];
string A, B;

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> A >> B;
    for(int i=0;i<=n;i++) for(int j=0;j<=2;j++) fill(dp[i][j], dp[i][j]+3, n);
	dp[0][0][2] = 0;

    for(int i=1;i<=n;i++) {
        int u = B[i-1]-'0';

        for(int j=0;j<2;j++) dp[i][j][u] = min(dp[i-1][j][2]+1, dp[i-1][j][u]);
		dp[i][1][u] = min(dp[i][1][u], dp[i-1][0][2]+2);

		if(A[i-1] == B[i-1]) {
			dp[i][0][2] = min(dp[i-1][0][2], dp[i-1][1][2]);
			dp[i][1][2] = dp[i][1][u];
		} else {
			dp[i][0][2] = dp[i][0][u];
			dp[i][1][2] = min({dp[i-1][1][2], dp[i][1][u], dp[i-1][0][2]+1});
		}
    }

    cout << min(dp[n][0][2], dp[n][1][2]);
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...