Submission #129113

#	Time	Username	Problem	Language	Result	Execution time	Memory
129113		Mahmoud_Adel	Lamps (JOI19_lamps)	C++14	4 / 100	243 ms	90604 KiB

lamp

#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
typedef long long ll;
const int N = 1e6+5;
int n, dp[N][5], nxt[N];
string a, b;
void operate()
{
	int one = n, zero = n;
	for(int i=n-1; i>=0; i--)
	{
		if(b[i] == '1') one = i, nxt[i] = zero;
		else zero = i, nxt[i] = one;
	}
}
int sol(int i, int t)
{
	if(i == n) return 0;
	int &ret = dp[i][t];
	if(ret != -1) return ret;
	ret = sol(nxt[i], t)+1;
	if(t == 3)
	{
		if(a[i] == b[i]) ret = min(ret, sol(i+1, t));
		else if(b[i] == '0') ret = min(ret, min(sol(i+1, 2), sol(i+1, 0))+1);
		else ret = min(ret, min(sol(i+1, 2), sol(i+1, 1))+1);
	}
	if(t == 2)
	{
		if(a[i] == b[i]) ret = min(ret, sol(i+1, 3));
		else ret = min(ret, sol(i+1, t));
	}
	if(t == 1)
	{
		if(b[i] == '1') ret = min(ret, sol(i+1, t));
		else if(b[i] == a[i]) ret = min(ret, sol(i+1, 3));
		else ret = min(ret, min(sol(i+1, 2), sol(i+1, 0))+1);
	}
	if(!t)
	{
		if(b[i] == '0') ret = min(ret, sol(i+1, t));
		else if(a[i] == b[i]) ret = min(ret, sol(i+1, 3));
		else ret = min(ret, min(sol(i+1, 2), sol(i+1, 1))+1);
	}
	return ret;
}
int main()
{
	memset(dp, -1, sizeof dp);
	cin >> n >> a >> b;
	operate();
	cout << sol(0, 3) << endl;
}

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