Submission #390563

#TimeUsernameProblemLanguageResultExecution timeMemory
390563peijarLamps (JOI19_lamps)C++17
100 / 100
106 ms51496 KiB
#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;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...