Submission #623713

#TimeUsernameProblemLanguageResultExecution timeMemory
623713ArsaLamps (JOI19_lamps)C++14
47 / 100
27 ms20936 KiB
#include<bits/stdc++.h>
using namespace std;

const int N = 3e5+10;

int n;
string a,b;
int dp[N][6];
int ans = 1e9;

void Input();
void Dp();
int C(int);
int Esh(int,int);
bool F(char,char,int);
void Output();

int main(){
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	Input();
	Dp();
	Output();
}

void Input(){
	cin >> n >> a >> b;
}

void Dp(){
	//base
	for(int i = 0;i < 6;i++)
		if(F(a[0], b[0], i))
			dp[0][i] = C(i);
		else
			dp[0][i] = -1;
	
	//dp
	for(int i = 1;i < n;i++)
		for(int j = 0;j < 6;j++)
			if(F(a[i], b[i], j)){
				dp[i][j] = n;
				for(int k = 0;k < 6;k++)
					if(dp[i-1][k] != -1)
						dp[i][j] = min(dp[i][j], dp[i-1][k] + C(j) - Esh(k, j));		
			}else
				dp[i][j] = -1;
}

int C(int x){
	int res = 0;
	if(x > 1) res++;
	if(x % 2) res++;
	return res;
}

int Esh(int k, int j){
	int res = 0;
	if(k % 2 and j % 2) res++;	
	if(k/2 == j/2 and k/2) res++;
	return res;
}

bool F(char x,char y,int f){
	if((f == 2 or f == 5) and y == '0')
		return true;
	else if((f == 3 or f == 4) and y == '1')
		return true;
	else if(f == 0 and x == y)
		return true;
	else if(f == 1 and x != y)
		return true;
	return false;
}

void Output(){	
	for(int i = 0;i < 6;i++)
		if(dp[n-1][i] != -1)
			ans = min(ans, dp[n-1][i]);
	cout << ans << endl;	
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...