제출 #158553

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
158553		Mounir	Lamps (JOI19_lamps)	C++14	100 / 100	190 ms	29944 KiB

lamp

#include <bits/stdc++.h>
#define chmin(x, v) x = min(x, v)
using namespace std;

const int TAILLE_CHAINE = 1e6 + 1;
int dp[TAILLE_CHAINE][3][2];
int lenChaine;
bool depart[TAILLE_CHAINE], arrivee[TAILLE_CHAINE];
string d, a;

void litEntree();
void solve();

int main()
{
	litEntree();
	solve();
	return 0;
}

void litEntree()
{
	cin >> lenChaine;
	cin.ignore();
	
	
	getline(cin, d);
	for (int idCara = 0; idCara < lenChaine; ++idCara){
		depart[idCara] = d[idCara] - '0';
	//	cout << depart[idCara];
	}
	
	//cin.ignore();
	getline(cin, a);
	for (int idCara = 0; idCara < lenChaine; ++idCara)
		arrivee[idCara] = a[idCara] - '0';
	for (int j = 0; j < 3; ++j)
		for (int k = 0; k < 2; ++k)
			if (j || k)
				dp[0][j][k] = 1e6 + 5;
}

void solve()
{
	for (int idCara = 1; idCara <= lenChaine; ++idCara)
	{
		for (int j = 0; j < 3; ++j)
			for (int k = 0; k < 2; ++k)
			{
				dp[idCara][j][k] = 1e6 + 5;
				if (j == 0 && k != (arrivee[idCara - 1]^depart[idCara - 1]))
					continue;
				if (j == 1 && k != arrivee[idCara - 1])continue;
				if (j == 2 && k == arrivee[idCara - 1])continue;
				
				for (int newJ = 0; newJ < 3; ++ newJ)
				{
					chmin(dp[idCara][j][k], dp[idCara - 1][newJ][0] + (newJ != j && j > 0) +k);
					chmin(dp[idCara][j][k], dp[idCara - 1][newJ][1] + (newJ != j && j > 0));
				}
			}
			
		
		/*cout << "-------\n";
		for (int i = 0; i < 3; ++i){
			for (int j = 0; j < 2; ++j)
				cout << dp[idCara][i][j] << " ";
			cout << endl;
		}
		cout << "---\n";*/
	}
	
	int mini = 1e6 + 10;
	for (int i = 0; i < 3; ++i)
		for (int j = 0; j < 2; ++j)
			chmin(mini, dp[lenChaine][i][j]);
	
	cout << mini << endl;
}

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