Submission #329729

#	Time	Username	Problem	Language	Result	Execution time	Memory
329729		Rainbowbunny	Lamps (JOI19_lamps)	C++17	100 / 100	118 ms	35888 KiB

lamp

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

int n;
string c, d;
int cost[6][6];
int a[1000005], b[1000005];
int dp[1000005][6];
int ans = 1e9;

int main()
{
	for(int i = 0; i < 6; i++)
	{
		for(int j = 0; j < 6; j++)
		{
			if(i / 2 != j / 2 && j / 2 != 0)
			{
				++cost[i][j];
			}
			if(i % 2 != j % 2 && j % 2 != 0)
			{
				++cost[i][j];
			}
		}
	}
	cin >> n >> c >> d;
	for(int i = 1; i <= n; i++)
	{
		a[i] = c[i - 1] - '0';
		b[i] = d[i - 1] - '0';
	}
	for(int i = 1; i <= 5; i++)
	{
		dp[0][i] = 1e9;
	}
	for(int i = 1; i <= n; i++)
	{
		for(int j = 0; j < 6; j++)
		{
			dp[i][j] = 1e9;
			int cur = a[i];
			if(j / 2 == 1)
			{
				cur = 0;
			}
			else if(j / 2 == 2)
			{
				cur = 1;
			}
			if(cur ^ (j & 1) == b[i])
			{
				for(int k = 0; k < 6; k++)
				{
					dp[i][j] = min(dp[i][j], dp[i - 1][k] + cost[k][j]);
				}
			}
		}
	}
	for(int i = 0; i < 6; i++)
	{
		ans = min(ans, dp[n][i]);
	}
	cout << ans;
}

Compilation message (stderr)

lamp.cpp: In function 'int main()':
lamp.cpp:51:21: warning: suggest parentheses around comparison in operand of '^' [-Wparentheses]
   51 |    if(cur ^ (j & 1) == b[i])
      |             ~~~~~~~~^~~~~~~

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