Submission #1304920

#TimeUsernameProblemLanguageResultExecution timeMemory
1304920AksLolCodingLamps (JOI19_lamps)C++17
100 / 100
72 ms14832 KiB
#include <iostream>

using namespace std;
const int N = 1<<20;
int dp[N][3];

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

	for (int i=0;i<N*3;i++)
		dp[i / 3][i % 3] = N;

	dp[0][2] = 0;
	
	for (int i=1;i<=n;i++){
		for (int j : {0, 1, 2}){
			char prv = char(j + '0');
			if (i > 1 and j == 2)
				prv = a[i - 2];

			for (int k : {0, 1, 2}){
				int cst = dp[i-1][j];
				if (j != k and k != 2)
					cst++;

				char cur = char(k + '0');
				if (k == 2)
					cur = a[i - 1];
				if (cur != b[i-1] and (i == 1 or prv == b[i-2]))
					cst++;

				if (dp[i][k] > cst)
					dp[i][k] = cst;
			}
		}
	}

	cout<<min(dp[n][0], min(dp[n][1], dp[n][2]))<<'\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...