Submission #1308580

#	Time	Username	Problem	Language	Result	Execution time	Memory
1308580		arashmemar	Lamps (JOI19_lamps)	C++20	100 / 100	94 ms	25856 KiB

lamp

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

const int minn = 1e6 + 100;

struct ans
{
	int a, b;
	ans (int a = 0, int b = 0) : a(a), b (b) {};

	bool operator < (ans other)
	{
		if (a < other.a)
		{
			return 1;
		}
		if (a > other.a)
		{
			return 0;
		}
		return b >= other.b;
	}

	ans inc()
	{
		ans ret = *this;
		ret.a++;
		return ret;
	}

	ans dec()
	{
		ans ret = *this;
		ret.a--;
		return ret;
	}
};

ans min(ans a, ans b)
{
	if (a < b)
	{
		return a;
	}
	return b;
}

ans dp[minn], pd[minn], pdd[minn];

bool a[minn], b[minn];

void inp(bool &x)
{
	char y;
	cin >> y;
	x = (y == '1');
	return ;
}

int main()
{
	ans minf(0, -1);
	int n;
	cin >> n;
	for (int i = 1;i <= n;i++)
	{
		inp(a[i]);
	}
	for (int i = 1;i <= n;i++)
	{
		inp(b[i]);
	}

	pd[0] = pdd[0] = {1, 0};

	for (int i = 1;i <= n;i++)
	{
		dp[i] = min(dp[i - 1], min(pd[i - 1], pdd[i - 1]));
		if ((dp[i].b & 1) ^ (a[i] ^ b[i]))
		{
			dp[i].b--;
		}
		if (dp[i].b == -1)
		{
			dp[i].b = 1;
			dp[i].a++;
		}

		pd[i] = min(pd[i - 1], min(dp[i - 1].inc(), pdd[i - 1].inc()));
		if ((pd[i].b & 1) ^ b[i])
		{
			pd[i].b--;
		}
		if (pd[i].b == -1)
		{
			pd[i].b = 1;
			pd[i].a++;
		}

		pdd[i] = min(pdd[i - 1], min(dp[i - 1].inc(), pd[i - 1].inc()));
		if ((pdd[i].b & 1) ^ 1 ^ b[i])
		{
			pdd[i].b--;
		}
		if (pdd[i].b == -1)
		{
			pdd[i].b = 1;
			pdd[i].a++;
		}
	}
	cout << min(dp[n].a, min(pd[n].a, pdd[n].a));
}

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