Submission #129168

#	Time	Username	Problem	Language	Result	Execution time	Memory
129168		Mahmoud_Adel	Lamps (JOI19_lamps)	C++14	100 / 100	271 ms	90188 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 == 2 && nxt[i] != n)
	{
		if(b[i] == '0') ret = min(ret, sol(nxt[i], 1)+1);
		else ret = min(ret, sol(nxt[i], 0)+1);
	}
	if((t == 1 && b[i] == '0') || (t == 0 && b[i] == '1'))
		ret = min(ret, sol(nxt[i], 2)+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: 6 / 6
• Subtask 2: 41 / 41
• Subtask 3: 4 / 4
• Subtask 4: 49 / 49