Submission #1294639

#	Time	Username	Problem	Language	Result	Execution time	Memory
1294639		Jawad_Akbar_JJ	Lamps (JOI19_lamps)	C++20	47 / 100	35 ms	5672 KiB

lamp

#include <iostream>

using namespace std;
const int N = 1<<18;
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';
}

• Subtask 1: 6 / 6
• Subtask 2: 41 / 41
• Subtask 3: 0 / 4
• Subtask 4: 0 / 49