Submission #623714

#	Time	Username	Problem	Language	Result	Execution time	Memory
623714		Arsa	Lamps (JOI19_lamps)	C++14	100 / 100	74 ms	27992 KiB

lamp

#include<bits/stdc++.h>
using namespace std;

const int N = 1e6+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;	
}

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