제출 #379562

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
379562		nafis_shifat	Lamps (JOI19_lamps)	C++14	100 / 100	478 ms	135636 KiB

lamp

#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
using namespace std;
const int mxn=1e5+5;
const int inf=1e9;

int get(int x,int op) {
	if(op == 0) return 0;
	if(op == 1) return 1;
	if(op == 2) return x ^ 1;
	return x;
}
int op(int a) {
	return a != 3;
}
int op(int a,int b) {
	return (a != 3) + (b != 3);
}
int main() {
	int n;
	cin >> n;
	int dp[n + 1][4][4][2] = {};

	int a[n + 1];
	int b[n + 1];

	for(int i = 1; i <= n; i++) {
		char c;
		cin >> c;
		c -= '0';
		a[i] = c;
	}

	for(int i = 1; i <= n; i++) {
		char c;
		cin >> c;
		c -= '0';
		b[i] = c;
	}

	int lm0 = inf;
	int lm1 = inf;



	for(int i = 0; i < 4; i++) {
		for(int j = 0; j < 4; j++) {
			int x = get(a[1],i);
			int y = get(x,j);

			if(y == b[1]) {
				dp[1][i][j][0] = op(i,j);
				dp[1][i][j][1] = inf;
			}
			else {
				dp[1][i][j][1] = op(i,j) + 1;
				dp[1][i][j][0] = inf;
			}
			lm0 = min(lm0,dp[1][i][j][0]);
			lm1 = min(lm1,dp[1][i][j][1]);
		}
	}


	for(int i = 2; i <= n; i++) {
		int cm0 = inf,cm1 = inf;
		for(int j = 0; j < 4; j++) {
			for(int k = 0; k < 4; k++) {
				int x = get(a[i],j);
			    int y = get(x,k);
			    if(y != b[i]) {
			    	dp[i][j][k][0] = inf;
			    	int &r = dp[i][j][k][1];
			    	r = dp[i - 1][j][k][1];
			    	r = min(r,lm1 + op(j,k));
			    	for(int x = 0; x < 4; x++) r = min(r,min(dp[i - 1][x][j][0] + 1,dp[i - 1][x][j][1]) + op(k));
			    	for(int x = 0; x < 4; x++) r = min(r,min(dp[i - 1][j][x][0] + 1,dp[i - 1][j][x][1]) + op(k));
			    	cm1 = min(cm1,dp[i][j][k][1]);
			    }
			    else {
			    	dp[i][j][k][1] = inf;
			    	int &r = dp[i][j][k][0];
			    	r = dp[i - 1][j][k][0];
			    	r = min(r,min(lm0,lm1) + op(j,k));
			    	for(int x = 0; x < 4; x++) r = min(r,min(dp[i - 1][x][j][0],dp[i - 1][x][j][1]) + op(k));
			    	for(int x = 0; x < 4; x++) r = min(r,min(dp[i - 1][j][x][0],dp[i - 1][j][x][1]) + op(k));
			    	cm0 = min(cm0,dp[i][j][k][0]);
			    }				
			}
		}
		lm0 = cm0;
		lm1 = cm1;
	}
	
	cout<<min(lm0,lm1)<<endl;



}

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