제출 #379559

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
379559		nafis_shifat	Lamps (JOI19_lamps)	C++14	10 / 100	287 ms	72828 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] = {};

	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 lm = 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] = op(i,j);
			else dp[1][i][j] = inf;
			lm = min(lm,dp[1][i][j]);
		}
	}




	for(int i = 2; i <= n; i++) {
		int cm = 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] = inf;
			    else {
			    	int &r = dp[i][j][k];
			    	r = dp[i - 1][j][k];
			    	r = min(r,lm + op(j,k));
			    	for(int x = 0; x < 4; x++) r = min(r,dp[i - 1][x][j] + op(k));
			    	for(int x = 0; x < 4; x++) r = min(r,dp[i - 1][j][x] + op(k));
			    	cm = min(cm,dp[i][j][k]);

			    }				
			}
		}
		lm = cm;
	}
	
	cout<<lm<<endl;



}

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