제출 #390563

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
390563		peijar	Lamps (JOI19_lamps)	C++17	100 / 100	106 ms	51496 KiB

lamp

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

const int MAXN = 1e6+1;

int dp[MAXN][2][3];

signed main(void)
{
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	int nbCarac;
	cin >> nbCarac;
	string have, want;
	cin >> have >> want;
	vector<bool> from(nbCarac), to(nbCarac);
	for (int iCarac(0); iCarac < nbCarac; ++iCarac)
		from[iCarac] = have[iCarac] - '0', to[iCarac] = want[iCarac] - '0';

	for (int i(0); i < MAXN; ++i)
		for (int j(0); j < 2; ++j)
			for (int k(0); k < 3; ++k)
				dp[i][j][k] = 1e9;
	dp[0][0][2] = 0;
	
	for (int nbVus(1); nbVus <= nbCarac; ++nbVus)
		for (int flip(0); flip < 2; ++flip)
			for (int set(0); set < 3; ++set)
				if ( (set == 2 and (from[nbVus-1] ^ flip) == to[nbVus-1])
						or (set != 2 and (set ^ flip) == to[nbVus-1]))
				{
					int &cur = dp[nbVus][flip][set];

					for (int prvFlip(0); prvFlip < 2; ++prvFlip)
						for (int prvSet(0); prvSet < 3; ++prvSet)
						{
							int cost = (!prvFlip and flip) + (set != 2 and set != prvSet);
							cur = min(cur, cost + dp[nbVus-1][prvFlip][prvSet]);
						}
				}

	int ret = 1e9;
	for (int i(0); i < 2; ++i)
		for (int j(0); j < 3; ++j)
			ret = min(ret, dp[nbCarac][i][j]);
	cout << ret << endl;
}

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