Submission #142545

#	Time	Username	Problem	Language	Result	Execution time	Memory
142545		aminra	Lamps (JOI19_lamps)	C++17	100 / 100	89 ms	16288 KiB

lamp

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const int MAXN = (int)1e6 + 3;
const ll infint = (int)1e9 + 3;
const int MOD = (int)1e9 + 7;
const ll inf = (ll)1e18 + 3;
int dp[MAXN][3], n;
string A, B;
int toggle(int i, int j)
{
	if(j == 2)
		return A[i] != B[i];
	if(j == 0)
		return B[i] != '0';
	if(j == 1)
		return B[i] != '1';
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> n >> A >> B;
	dp[n - 1][0] = 1 + toggle(n - 1, 0);
	dp[n - 1][1] = 1 + toggle(n - 1, 1);
	dp[n - 1][2] = toggle(n - 1, 2);
	for (int i = n - 2; i >= 0; i--)
		for (int j = 0; j <= 2; j++)
		{
			dp[i][j] = infint;
			for (int k = 0; k <= 2; k++)
				dp[i][j] = min(dp[i][j], dp[i + 1][k] + (j != 2 && k != j) + (toggle(i, j) && !toggle(i + 1, k)));
		}
	cout << min(dp[0][0], min(dp[0][1], dp[0][2]));
}

Compilation message (stderr)

lamp.cpp: In function 'int toggle(int, int)':
lamp.cpp:19:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

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